Dada una secuencia $A_1, A_2, \ldots, A_N$ de longitud $N$ y un entero $M$. Procesar $Q$ consultas. Cada consulta consta de dos enteros $d$ y $k$, y se realizan las siguientes operaciones en orden:

• Construir una nueva secuencia $B_i = (A_i + d) \bmod M$ ($1 \le i \le N$).
• Para todo $i$ ($1 \le i \le N$), definir el $i$-ésimo sufijo como $B_i, B_{i+1}, \ldots, B_N$.
• Imprimir el índice del $K$-ésimo sufijo lexicográficamente más pequeño de la secuencia $B$.

Entrada

La primera línea contiene la longitud de la secuencia $N$ y el entero $M$.

La segunda línea contiene $A_1, A_2, \ldots, A_N$.

La tercera línea contiene el número de consultas $Q$.

Las siguientes $Q$ líneas contienen cada una una consulta $d$ y $k$.

Salida

Para cada consulta, imprimir el índice del $K$-ésimo sufijo lexicográficamente más pequeño de la secuencia $B$, cada uno en una línea nueva.

Nota

En la primera consulta, la secuencia $B = [5, 2, 0, 5, 5]$. Ordenando todos los sufijos lexicográficamente se obtiene $[0, 5, 5]$, $[2, 0, 5, 5]$, $[5]$, $[5, 2, 0, 5, 5]$, $[5, 5]$. El 4.º sufijo lexicográficamente más pequeño tiene índice $1$.

Ejemplos

Entrada 1

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

Salida 1

1
1
5