「Wdoi-2」来自地上的支援

题目背景

波光粼粼的山顶湖与庄严神圣的神社之下,是一座复合型活火山。 沿幻想风穴而下,便能到达火山之下,废弃已久的地狱原址。 >在旧地狱中,有一座大都市。那里是旧地狱还是地狱的时候在那工作的众鬼们居住的地方,只有那里亡者们是无法踏入去的。后来地狱体制改革,机构搬离了这个地方。 因为这个缘故这块地狱变成了废墟,但却有一部分看上了那里的妖怪擅作主张占领了那里,于是就成了如今的旧地狱了。 这里比地上更没有秩序可言。悍匪恶霸,特别是惹人类讨厌的家伙都喜欢搬到这边定居下来。 自旧地狱喷泻而出的间歇泉,给妖怪之山带来了优良的温泉,也喷出了大量的怨灵。 为了解决这次异变,乐园的巫女和普通的魔法使结伴而行,在来自地上的支援下,自幻想风穴直冲地底。 先后结(bao)识(da)了黑暗洞窟中的明亮之网、地壳下的嫉妒心、人们所谈论的怪力乱神后,二人来到了遗址中心的洋馆,地灵殿。 受这里主人的指引,二人来到了位于深处的间歇泉地下中心。

题目描述

### 简要题意 给定正整数 $n$、$v$ 和长度为 $n$ 的数组 $\{A_i\}$。 有一个长度为 $n$ 的数组 $B$,初始值与 $A$ 相同。 执行 $n$ 次操作,第 $i$ 次操作在 $[1,i]$ 中按如下规则选取一个正整数 $j$,然后把 $B_j$ 变成 $B_j+v$: - 选取 $B_j$ 最大的 $j$。 - $B_j$ 相同时选择 $A_j$ 最大的 $j$。 - $A_j,B_j$ 均相同,选择较小的 $j$。 我们称这是选中了一次 $j$。 有 $m$ 次询问,每次询问给定 $x_i,k_i$。表示求最小的 $s$,使得**若**将 $A_{x_i}$ 的初始值改为 $s$(注意此时 $B_{x_i}$ 的初始值也会跟着改变),$x_i$ 至少被选中 $k_i$ 次,或报告不存在(**结果为** $0$)。请注意,$s$ 不存在最小值时也是报告不存在(**结果为** $0$)。 询问之间互相独立,也就是每次询问不会对 $A_{x_i}$ 和 $B_{x_i}$ 产生实质性更改。 ### 原始题意 到达控制中心之后,主角组和灵乌路空进行了激烈的狗斗大赛。负责技术维护的河童需要接受荷取来自地上指挥部的指令,保障生产安全。 具体地,有 $n$ 个核反应机组依次排开,第 $i$ 个机组的活动强度为 $A_i$。为了维护平衡,控制系统依次操作 $n$ 次,第 $i$ 次操作会在前 $i$ 个机组中找到一个**当前活动度最高的**机组,进行一次调节平衡操作,并将其活动度增加 $v$。倘若有多个机组活动度最高,就应当选择初始活动度**最大**的,若还是无法比较,则取编号最小。 为了在自动控制系统的基础上调节平衡,荷取会发出 $m$ 条指令,形如她每次会给出两个整数 $x_i,k_i$,表示她会修改第 $x_i$ 个机组的初始活动度。她希望通过修改(必须改成一个**非负整数** $s$)后,$x_i$ 号机组至少被平衡 $k_i$ 次。如果无论如何都无法达到要求,那么结果就是 $0$;否则请求出满足条件的**最小的** $s$。

输入输出格式

输入格式


- 第一行有三个整数 $n, m, v$。 - 接下来一行,有 $n$ 个整数,描述 $a_i$。 - 接下来 $m$ 行,每行有两个整数 $x_i,k_i$,描述一次询问。

输出格式


- 一行,输出两个整数,表示所有结果的**异或和**与**加法和**。

输入输出样例

输入样例 #1

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

输出样例 #1

7 7

输入样例 #2

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

输出样例 #2

245 1177

说明

### 样例 1 解释 对于第一次询问,我们将 $A_3$ 修改为 $7$。 - 第一次操作选择了位置 $1$,于是 $B_1$ 变为 $4$。 - 第二次操作选择了位置 $2$,于是 $B_2$ 变为 $7$。虽然操作前 $B_1=B_2$,但是 $A_2>A_1$,因此选择位置 $2$。 - 第三次操作选择了位置 $3$,于是 $B_3$ 变为 $10$。 - 第四次操作选择了位置 $3$,于是 $B_3$ 变为 $13$。 - 第五次操作选择了位置 $3$,于是 $B_3$ 变为 $16$。 - 第六次操作选择了位置 $3$,于是 $B_3$ 变为 $19$。 - 第七次操作选择了位置 $3$,于是 $B_3$ 变为 $22$。 于是位置 $3$ 一共被选择了 $5$ 次,满足题意。可以证明,如果把 $A_3$ 的初始值设为 $6$,无法达成要求。于是该询问结果为 $7$。 对于第二个询问,容易发现不可能有 $4$ 次以上操作选择位置 $6$。因此该询问结果为 $0$。 $7\oplus 0=7$,$7+0=7$,因此输出 $7,7$。 ### 数据范围 $$ \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}$$ 对于全部数据,满足 $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$。 **本题 IO 量较大,请选择合适的输入方式。**