長さ $N$ の数列 $A_1, A_2, \ldots, A_N$ と整数 $M$ が与えられます。$Q$ 個のクエリを処理してください。各クエリは 2 つの整数 $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$ と定義する。
• 数列 $B$ の接尾辞を辞書順に並べたとき、$K$ 番目に小さい接尾辞のインデックスを出力する。

入力

1 行目には、数列の長さ $N$ と整数 $M$ が含まれます。

2 行目には、$A_1, A_2, \ldots, A_N$ が含まれます。

3 行目には、クエリの個数 $Q$ が含まれます。

次の $Q$ 行には、各クエリの $d$ と $k$ が含まれます。

出力

各クエリについて、数列 $B$ の接尾辞を辞書順に並べたときの $K$ 番目に小さい接尾辞のインデックスを、それぞれ新しい行に出力してください。

注記

最初のクエリでは、数列 $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