Sequence and Queries 40

You are given a sequence $A_1, A_2, \ldots, A_N$ of length $N$ and an integer $M$. Each query consists of two integers $d$ and $k$. For each query, perform the following steps in order.

• Build a new sequence $B_i = (A_i + d) \bmod M$ for $1 \le i \le N$.
• For every $i$ ($1 \le i \le N$), define the $i$-th suffix as $B_i, B_{i+1}, \ldots, B_N$.
• Output the suffix number of the sequence $B$ that is $k$-th smallest in lexicographic order.

The first line contains $N$ and $M$.

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

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

Each of the next $Q$ lines contains one query, the integers $d$ and $k$.

For each query, print on its own line the suffix number of the $k$-th smallest sequence $B$ in lexicographic order.

• $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$

In the first query, the sequence is $B = [5, 2, 0, 5, 5]$. Sorting all suffixes in lexicographic order gives $[0, 5, 5]$, $[2, 0, 5, 5]$, $[5]$, $[5, 2, 0, 5, 5]$, $[5, 5]$. The suffix in 4th place has number 1.