Задан массив $a$, состоящий из $n$ чисел.

Кроме того, вам дано $q$ запросов. Запрос представляет собой два числа $l$ и $r$. Для каждого запроса требуется найти такой подотрезок $[l'; r']$, что $l \le l' \le r' \le r$, а так же найдётся такое положительное целое число $x$, что $x > 1$ и остаток от деления на $x$ у всех чисел на подотрезке одинаковый. Найденный подотрезок должен быть максимально возможной длины.

Входные данные

В первой строке записаны числа $n$ и $k$ ($1 \le n \le 3 \cdot 10^5;\ 0 \le k \le 10^9$) – длина массива и коэффициент пересчёта (ниже описано, зачем он нужен).

Во второй строке записаны числа $a_1, a_2, \dots, a_n$ – элементы массива. ($1 \le a_i \le 10^{18}$)

В третьей строке записано число $q$ – количество запросов ($1 \le q \le 3 \cdot 10^5$).

В каждой из следующих строк записаны по два числа $l_i$ и $r_i$ – границы для $i$-того запроса ($1 \le l, r \le n$). Их необходимо пересчитать.

Для первого запроса числа $l$ и $r$ равны числам $l_1$ и $r_1$.

Для $i$-того запроса число $l$ равно $(l_i + len_{i - 1} * k - 1) \mod n + 1$, где $len_{i - 1}$ - длина подотрезка, выведенного вами в ответ на предыдущий запрос.

Число $r$ для этого запроса считается аналогично: $(r_i + len_{i - 1} * k - 1) \mod n + 1$.

Если после пересчёта окажется, что $l > r$, то их значения стоит поменять местами.

Выходные данные

В ответ на каждый запрос выведите по два числа $l'$ и $r'$ – границы искомого подотрезка.

Подзадачи