Étant donné une séquence $A_1, A_2, \ldots, A_N$ de longueur $N$ et un entier $M$. Traiter $Q$ requêtes. Chaque requête consiste en deux entiers $d$ et $k$, et les opérations suivantes sont effectuées dans l'ordre :

• Construire une nouvelle séquence $B_i = (A_i + d) \bmod M$ ($1 \le i \le N$).
• Pour tout $i$ ($1 \le i \le N$), définir le $i$-ème suffixe comme $B_i, B_{i+1}, \ldots, B_N$.
• Afficher l'indice du $K$-ème plus petit suffixe dans l'ordre lexicographique de la séquence $B$.

Entrée

La première ligne contient la longueur de la séquence $N$ et l'entier $M$.

La deuxième ligne contient $A_1, A_2, \ldots, A_N$.

La troisième ligne contient le nombre de requêtes $Q$.

Les $Q$ lignes suivantes contiennent chacune une requête $d$ et $k$.

Sortie

Pour chaque requête, afficher l'indice du $K$-ème plus petit suffixe dans l'ordre lexicographique de la séquence $B$, chacun sur une nouvelle ligne.

Remarque

Dans la première requête, la séquence $B = [5, 2, 0, 5, 5]$. Trier tous les suffixes par ordre lexicographique donne $[0, 5, 5]$, $[2, 0, 5, 5]$, $[5]$, $[5, 2, 0, 5, 5]$, $[5, 5]$. Le 4e plus petit suffixe a pour indice $1$.

Exemples

Entrée 1

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

Sortie 1

1
1
5