Хэрвээ бид хамгийн ихдээ ямар нэгэн өөр $k$ ширхэг тоо нэмсний дараа ялгавар нь $d$ байх арифметик прогресс байх дараалал ялгаж авч чадаж байвал энэ бүхэл тоон дарааллыг $k$-$d$ сайн дараалал гэнэ.

Танд $n$ бүхэл тоонуудаас бүрдсэн ямар нэг $a$ дараалал байна. Таны даалгавар бол $k$-$d$ сайн дараалал байх хамгийн урт үргэлжилсэн дэд хэсгийг олох юм.

Оролт

Эхний мөр нь зайгаар тусгаарлагдсан $n, k, d$ ($1 ≤ n ≤ 2*10^{5}; 0 ≤ k ≤ 2*10^{5}; 0 ≤ d ≤ 10^{9}$) гурван бүхэл тоог агуулна. Хоёр дахь мөр нь анхны дараалал болох зайгаар тусгаарлагдсан $n$ ширхэг бүхэл тоонууд агуулна: $a_{1}, a_{2}, ..., a_{n}$ ($ - 10^{9} ≤ a_{i} ≤ 10^{9}$).

Гаралт

Зайгаар тусгаарлагдсан $l, r$ ($1 ≤ l ≤ r ≤ n$) хоёр бүхэл тоо хэвлэнэ.$a_{l}, a_{l + 1}, ..., a_{r}$ хамгийн урт дэд хэсэг нь $k$-$d$ сайн дараалал юм.

Хэрвээ олон оновчтой хариулт байгаа бол $l$-н хамгийн бага утгатай нэгийг хэвлэнэ.

Эхний жишээний хариулт нь 2, 8, 6 тоонуудыг агуулсан дэд хэсэг. 4 тоог нэмсэний дараа 2, 4, 6, 8 дарааллыг ялгаж авч болно. Энэ нь 2 зөрүүтэй арифметик прогресс юм.