P8539 "Wdoi-2" Support from the Surface

Beneath the shimmering summit lake and the solemn, sacred shrine lies a composite active volcano. Going down along the Gensokyo Vent, you can reach the long-abandoned former site of Hell beneath the volcano. > In Old Hell, there is a large metropolis. It was where the oni who worked there lived when it was still called Hell or Old Hell, and only there the dead could not set foot. Later, after a reform of the Hell system, the organizations moved away from this place. > For this reason, this part of Hell became ruins, but some youkai took a liking to it and occupied it without permission, and thus it became today’s Old Hell. > There is even less order here than on the surface. Bandits and bullies, especially those disliked by humans, all like to move here and settle down. The geysers erupting from Old Hell bring excellent hot springs to Youkai Mountain, and also spew out a large number of vengeful spirits. To resolve this incident, the shrine maiden of Paradise and an ordinary magician travel together. With support from the surface, they charge straight into the underground from the Gensokyo Vent. After meeting (and fighting) the bright web in the dark cave, the jealousy beneath the crust, and the strange gods and demons people talk about, the two arrive at the mansion in the center of the ruins, Chireiden. Guided by the master of this place, they reach the underground center of the geyser deep within.

## 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.

- 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 one line with two integers, representing the **xor sum** and the **sum** of all results.

## 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