C. Тавас ба Карафс

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Карафс бол $1 × h$ хэмжээтэй нэгэн төрлийн хүнсний ногоо юм. Таваполисын хүмүүс Карафст маш дуртай бөгөөд тэд бараг бүх төрлийн хоолондоо Карафс хийдэг байна. Тавас өөрөө ч Карафст ухаангүй дуртай.

Карафс нь эерэг бүхэл тоон утга бүхий өндөртэй. Таваст хязгааргүй 1-суурьт Карафсуудын дараалал бий. $i$-р Карафсын өндөр $s_{i}=A+(i-1)×B$.

Өгөгдсөн $m$-ийн хувьд ихдээ $m$ ширхэг ялгаатай, идэгдээгүй байгаа Карафсуудын өндрийг $1$-ээр бууруулах "$m$ хэмжээгээр хазах" үйлдлийг тодорхойлъё. Карафсын өндрийг $0$ болоход уг карафсыг идэж дуусгасан гэж үзнэ.

Одоо СаДДас танаас $n$ ширхэг хүсэлт боловсруулж өгөхийг хүсч байна. Тэрээр хүсэлт бүрт танд $l$, $t$, $m$ тоонуудыг өгөх ба та эндээс $l ≤ r$ байх, мөн $s_{l}, s_{l + 1}, ..., s_{r}$ дарааллыг "$m$ хэмжээгээр хазах" үйлдлийг t-ээс ихгүй удаа хийж гүйцэтгэн идэх боломжтой байлгах хамгийн их $r$ тоог олох хэрэгтэй. Хэрэв $r$ тоо олдохгүй бол "-1" гэж хэвлээрэй.

Оролт

Эхний оролтын мөр нь $A$, $B$, $n$ ($1 ≤ A, B ≤ 10^{6}$, $1 ≤ n ≤ 10^{5}$) гурван бүхэл тоог агуулна.

Дараагийн $n$ мөрүүд нь асуулгуудын талаархи мэдээллийг агуулна. $i$-р мөр нь $i$-р хүсэлтийн $l, t, m$ ($1 ≤ l, t, m ≤ 10^{6}$) бүхэл тоонуудыг агуулна.

Гаралт

Хүсэлт бүрийн хариултыг нэг мөрөнд хэвлээрэй.

Орчуулсан: Солонго

Жишээ тэстүүд

Оролт
2 1 4
1 5 3
3 3 10
7 10 2
6 4 8
Гаралт
4
-1
8
-1
Оролт
1 5 2
1 5 10
2 7 4
Гаралт
1
2
Сэтгэгдлүүдийг ачааллаж байна...