Codeforces Round #696 (Div. 2)
13:11:15 |
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