Description

MloVtry is very imaginative and often comes up with all kinds of strange ideas. However, as a "jun ruo" (noob), MloVtry often cannot solve the problems he proposes, so his dream of preparing a full problem set has been on hold.

Fortunately, MloVtry has some very strong friends ("dalao"), so he always asks them for help whenever he can.

Now MloVtry has $n$ ideas arranged in a line in his 2D brain. Each idea has a difficulty value $a[i]$; larger values mean harder problems.

MloVtry plans to consult $q$ experts, but he does not want to lower his standards by asking about ideas that are too easy, nor does he want to strain his relationships by asking about ideas that are too hard. Therefore, each time he will ask about the $k$-th easiest idea in the sequence (i.e., the idea with the $k$-th smallest difficulty).

MloVtry has a “pit” in his brain. Oddly enough, this pit helps him think, but it causes the sequence $a[i]$ to be updated. Specifically, suppose the pit is at the $j$-th idea; then define a transformed array $b[i]$ by

• if $i \le j$, then $b[i] = a[i] - zz$;
• if $i > j$, then $b[i] = i + a[i] - j$.

If that were all, MloVtry would not be confused. The problem is that the pit jumps unpredictably, so he does not know which idea to ask about at any given time.

Now MloVtry gives you several queries—each is a pair $(at, k)$, meaning the pit is at position $at$, and he wants to ask about the $k$-th easiest idea. Please tell MloVtry what that idea’s difficulty is, i.e., the $k$-th smallest value in the transformed array $b$ defined by the current pit position.

To prevent “time-axis rolling,” the input $(at, k)$ for each query is obfuscated using the last answer. Let $lastans$ be the answer to the previous query (with $lastans = 0$ initially). For each query, before using $at$ and $k$, update them as follows: $at = ((at \oplus |lastans|) \bmod n) + 1$, $k = ((k \oplus |lastans|) \bmod n) + 1$, then compute the answer and set $lastans$ to this answer.

All arrays are 1-indexed.

Input Format

• The first line contains three integers $n$, $q$, $zz$.
• The second line contains $n$ integers $a[1], a[2], \dots, a[n]$.
• The next $q$ lines each contain two integers $at$ and $k$. For each query, first transform the given $at$ and $k$ using $lastans$ as: $at = ((at \oplus |lastans|) \bmod n) + 1$, $k = ((k \oplus |lastans|) \bmod n) + 1$, where $lastans$ is the previous query’s answer (with $lastans = 0$ initially).

Output Format

Output $q$ lines, each containing one integer: the answer to each query.

13 12 56
10100 12208 11766 11872 11336 10815 10710 11872 11536 11988 10100 10908 10815 
11 13
1 3
3 10
1 7
8 4
7 11
11 4
5 2
13 11
13 6
3 11
11 10

10044
11932
10918
11280
10044
10759
10827
11874
12152
10759
10044
10713

Hint

• All values fit in the 32-bit signed integer range.
• For 100% of the testdata, $n, q \le 60000$.
• For 40% of the testdata, $n, q \le 1000$.
• There may be duplicate values. For example, for the array 1 1 1 1 1 0 the 1st smallest value is $0$, and the 2nd through 6th smallest values are all $1$.

Translated by ChatGPT 5