길이가 $N$인 수열 $A_1, A_2, \ldots, A_N$과 정수 $M$이 주어진다. 쿼리 $Q$개를 수행해보자. 쿼리는 두 정수 $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$ 으로 정의한다.
• 사전 순으로 $K$번째로 작은 수열 $B$의 접미사 번호를 출력한다.

입력

첫째 줄에 수열의 크기 $N$과 정수 $M$이 주어진다.

둘째 줄에는 $A_1, A_2, \ldots, A_N$이 주어진다.

셋째 줄에는 쿼리의 개수 $Q$가 주어진다.

넷째 줄부터 $Q$개의 줄에 쿼리 $d$, $k$가 한 줄에 하나씩 주어진다.

출력

각각의 쿼리를 수행하면서 사전 순으로 $K$번째로 작은 수열 $B$의 접미사 번호를 한 줄에 하나씩 출력한다.

노트

첫 번째 쿼리에서 수열 $B = [5, 2, 0, 5, 5]$이다. 접미사를 모두 사전 순으로 정렬하면 $[0, 5, 5]$, $[2, 0, 5, 5]$, $[5]$, $[5, 2, 0, 5, 5]$, $[5, 5]$ 이다. 사전 순으로 $4$번째인 접미사의 번호는 $1$이다.

Sample

Input

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

Output

1
1
5