P4855 MloVtry's Idea

Click ~.

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.

- 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 $q$ lines, each containing one integer: the answer to each query.

- 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