Given a sequence $A_1, A_2, \ldots, A_N$ of length $N$ and an integer $M$. Process $Q$ queries. Each query consists of two integers $d$ and $k$, and the following operations are performed in order:

• Construct a new sequence $B_i = (A_i + d) \bmod M$ ($1 \le i \le N$).
• For all $i$ ($1 \le i \le N$), define the $i$-th suffix as $B_i, B_{i+1}, \ldots, B_N$.
• Output the index of the $K$-th lexicographically smallest suffix of the sequence $B$.

Input

The first line contains the sequence length $N$ and integer $M$.

The second line contains $A_1, A_2, \ldots, A_N$.

The third line contains the number of queries $Q$.

The next $Q$ lines each contain a query $d$ and $k$.

Output

For each query, output the index of the $K$-th lexicographically smallest suffix of the sequence $B$, each on a new line.

Note

In the first query, the sequence $B = [5, 2, 0, 5, 5]$. Sorting all suffixes lexicographically yields $[0, 5, 5]$, $[2, 0, 5, 5]$, $[5]$, $[5, 2, 0, 5, 5]$, $[5, 5]$. The 4th lexicographically smallest suffix has index $1$.

Examples

Input 1

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

Output 1

1
1
5