Dany jest ciąg $A_1, A_2, \ldots, A_N$ długości $N$ oraz liczba całkowita $M$. Należy obsłużyć $Q$ zapytań. Każde zapytanie składa się z dwóch liczb całkowitych $d$ i $k$, a kolejno wykonywane są następujące operacje:

• Konstruujemy nowy ciąg $B_i = (A_i + d) \bmod M$ ($1 \le i \le N$).
• Dla każdego $i$ ($1 \le i \le N$) definiujemy $i$-ty przyrostek jako $B_i, B_{i+1}, \ldots, B_N$.
• Wypisujemy indeks $K$-tego leksykograficznie najmniejszego przyrostka ciągu $B$.

Wejście

Pierwszy wiersz zawiera długość ciągu $N$ oraz liczbę całkowitą $M$.

Drugi wiersz zawiera $A_1, A_2, \ldots, A_N$.

Trzeci wiersz zawiera liczbę zapytań $Q$.

Kolejne $Q$ wierszy zawiera po jednym zapytaniu $d$ i $k$.

Wyjście

Dla każdego zapytania wypisz indeks $K$-tego leksykograficznie najmniejszego przyrostka ciągu $B$, każdy w osobnym wierszu.

Uwagi

W pierwszym zapytaniu ciąg $B = [5, 2, 0, 5, 5]$. Posortowanie wszystkich przyrostków leksykograficznie daje $[0, 5, 5]$, $[2, 0, 5, 5]$, $[5]$, $[5, 2, 0, 5, 5]$, $[5, 5]$. Czwarty leksykograficznie najmniejszy przyrostek ma indeks $1$.

Przykład

Wejście 1

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

Wyjście 1

1
1
5