Дана последовательность $A_1, A_2, \ldots, A_N$ длины $N$ и целое число $M$. Обрабатывается $Q$ запросов. Каждый запрос состоит из двух целых чисел $d$ и $k$, и выполняются следующие операции по порядку:

• Построить новую последовательность $B_i = (A_i + d) \bmod M$ ($1 \le i \le N$).
• Для всех $i$ ($1 \le i \le N$) определить $i$-й суффикс как $B_i, B_{i+1}, \ldots, B_N$.
• Вывести индекс $k$-го в лексикографическом порядке суффикса последовательности $B$.

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

Первая строка содержит длину последовательности $N$ и целое число $M$.

Вторая строка содержит $A_1, A_2, \ldots, A_N$.

Третья строка содержит количество запросов $Q$.

Следующие $Q$ строк содержат по одному запросу: $d$ и $k$.

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

Для каждого запроса выведите индекс $k$-го в лексикографическом порядке суффикса последовательности $B$, каждое на новой строке.

Примечание

В первом запросе последовательность $B = [5, 2, 0, 5, 5]$. Сортировка всех суффиксов в лексикографическом порядке даёт $[0, 5, 5]$, $[2, 0, 5, 5]$, $[5]$, $[5, 2, 0, 5, 5]$, $[5, 5]$. 4-й по лексикографическому порядку суффикс имеет индекс $1$.

Примеры

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

5 6
1 4 2 1 1
3
4 4
2 3
1 1

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

1
1
5