수열과 쿼리 40

길이가 $N$인 수열 $A_1, A_2, \ldots, A_N$과 정수 $M$이 주어진다. 각 쿼리는 정수 $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$의 접미사 번호를 한 줄에 하나씩 출력한다.

• $1 \le N \le 10^5$
• $1 \le M \le 10^9$
• $0 \le A_i < M$
• $1 \le Q \le 5 \cdot 10^5$
• $0 \le d \le 10^9$
• $1 \le k \le N$

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