Description

Brief Statement

You are given positive integers $n$, $v$, and an array $\{A_i\}$ of length $n$.

There is an array $B$ of length $n$, initially equal to $A$.
Perform $n$ operations. In the $i$-th operation, choose a positive integer $j$ in $[1,i]$ by the following rules, then change $B_j$ to $B_j+v$:

• Choose the $j$ with the maximum $B_j$.
• If $B_j$ ties, choose the $j$ with the maximum $A_j$.
• If both $A_j$ and $B_j$ tie, choose the smaller $j$.

We say that $j$ is selected once.

There are $m$ queries. Each query gives $x_i, k_i$. You need to find the minimum $s$ such that, if the initial value of $A_{x_i}$ is changed to $s$ (note that the initial value of $B_{x_i}$ will also change accordingly), then $x_i$ is selected at least $k_i$ times, or report that it does not exist (the result is $0$). Note that if $s$ has no minimum, you should also report that it does not exist (the result is $0$).

Queries are independent. That is, each query does not make any actual change to $A_{x_i}$ or $B_{x_i}$.

Original Statement

After arriving at the control center, the protagonists and Utsuho Reiuji engaged in a fierce dogfight contest. The kappa in charge of technical maintenance must receive instructions from Nitori, coming from the surface command, to ensure production safety.

Specifically, there are $n$ nuclear reactor units lined up in order. The activity intensity of the $i$-th unit is $A_i$. To maintain balance, the control system performs $n$ operations in order. In the $i$-th operation, it finds among the first $i$ units the unit with the currently highest activity, performs one balancing adjustment on it, and increases its activity by $v$. If multiple units have the highest activity, choose the one with the largest initial activity; if still indistinguishable, choose the one with the smallest index.

To adjust balance on top of the automatic control system, Nitori will issue $m$ commands. Each time she gives two integers $x_i, k_i$, meaning she will modify the initial activity of the $x_i$-th unit. She hopes that after the modification (it must be changed to a non-negative integer $s$), unit $x_i$ will be balanced at least $k_i$ times. If it is impossible no matter what, the result is $0$; otherwise, output the minimum $s$ that satisfies the condition.

Input Format

• The first line contains three integers $n, m, v$.
• The next line contains $n$ integers describing $a_i$.
• The next $m$ lines each contain two integers $x_i, k_i$, describing a query.

Output Format

• Output one line with two integers, representing the xor sum and the sum of all results.

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

7 7

10 10 9
14 91 84 13 97 92 23 64 31 10 
5 2
5 5
9 1
2 6
9 1
5 4
3 5
2 8
8 2
5 4

245 1177

Hint

Explanation for Sample 1

For the first query, we modify $A_3$ to $7$.

• The first operation chooses position $1$, so $B_1$ becomes $4$.
• The second operation chooses position $2$, so $B_2$ becomes $7$. Although before the operation $B_1=B_2$, we have $A_2>A_1$, so position $2$ is chosen.
• The third operation chooses position $3$, so $B_3$ becomes $10$.
• The fourth operation chooses position $3$, so $B_3$ becomes $13$.
• The fifth operation chooses position $3$, so $B_3$ becomes $16$.
• The sixth operation chooses position $3$, so $B_3$ becomes $19$.
• The seventh operation chooses position $3$, so $B_3$ becomes $22$.

Thus position $3$ is selected $5$ times in total, satisfying the requirement. It can be proven that if the initial value of $A_3$ is set to $6$, the requirement cannot be met. Therefore the answer to this query is $7$.

For the second query, it is easy to see that it is impossible to have $4$ or more operations selecting position $6$. Therefore the answer to this query is $0$.

$7\oplus 0=7$, $7+0=7$, so the output is $7,7$.

Constraints

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|}\hline \textbf{Subtask} & \bm{n,m\le} & \bm {a_i\le } & \bm{v\le} & \textbf{分值} \cr\hline 1 & 10 & 100 & 10 & 10 \cr\hline 2 & 100 & 5\times 10^3 & 50 & 20 \cr\hline 3 & 10^3 & 10^9 & 100 & 10 \cr\hline 4 & 10^5 & 10^9 & 100 & 25 \cr\hline 5 & 2\times 10^6 & 10^9 & 100 & 35 \cr\hline \end{array}$$

For all testdata, $1 \le n,m \le 2\times 10^6$, $1 \le v \le 100$, $1 \le a_i \le 10 ^ 9$, $1 \le x,k \le n$.

The I/O volume of this problem is large. Please choose an appropriate input method.

Translated by ChatGPT 5