题目描述

小 $\rm{A}$ 和小 $\rm{B}$ 喜欢玩游戏。

他们在数轴上玩游戏，数轴上的一些位置放着物品，最初他们有一个参数 $k$，保证 $k=0/1$。

接下来小 $\rm{A}$ 会选定一个位置 $x$，那么小 $\rm{B}$ 的位置就为 $x+k$，两个人会轮流取走物品，由小 $\rm{A}$ 先手。

对于当前操作的玩家，他会取走当前剩余物品中离自己的位置距离最近的一个物品，如果有两个物品距离相同，则他会取走位置更小的那个物品。

位置 $a$ 和 $b$ 的距离定义为 $|a-b|$。

最后，在所有物品都被取走后，小 $\rm{A}$ 想知道，他手上的物品位置的总和是多少。

但是，由于他们非常的闲，他们会进行 $q$ 次游戏，每次游戏结束后所有物品都会恢复原位置，对于每次游戏小 $\rm{A}$ 都想知道对于当前的位置 $x$，小 $\rm{B}$ 的位置 $x+k$，游戏完后小 $\rm{A}$ 手上的物品位置的总和。

输入格式

第一行三个数 $n,q,k$，表示数轴上存在 $n$ 个区间的物品，小 $\rm{A}$ 和小 $\rm{B}$ 的游戏次数和初始选定的参数。

接下来 $n$ 行，每行两个数 $l_i,r_i$ 表示在区间 $[l_i,r_i]$ 中的每个位置都有一个物品。

接下来 $q$ 行，每行一个数 $x$，表示此轮游戏小 $\rm{A}$ 的参数为 $x$，小 $\rm{B}$ 的参数为 $x+k$。

输出格式

设 $ans_i$ 表示第 $i$ 次询问的答案，那么输出一个整数表示 $\oplus_{i=1}^{q}i \times ans_i$。

4 2 1
4 5
7 8
10 11
13 13
6
8

16

7 6 0
2 2
4 5
7 8
9 9
13 13
15 15
18 20
19
15
18
17
11
5

468

见 game3.in/ans
这个样例满足子任务 2 的约束条件

见 game4.in/ans
这个样例满足子任务 4 的约束条件

提示

样例 1 解释

对于 $x=8$ 的询问。

小 $\rm{A}$ 在结束时手上的物品的位置为 $8,7,5,4$。

小 $\rm{B}$ 在结束时手上的物品的位置为 $10,11,13$。

因此结束时小 $\rm{A}$ 手上的物品位置的总和为 $8+7+5+4 = 24$。

对于 $x=6$ 的询问，答案为 $32$。

数据范围

对于所有数据，保证：$1 \le n \le 5000$，$1 \le q \le 2 \times 10^6$，$1 \le x \le 5 \times 10^6$，$1 \le l_i \le r_i \le 5 \times 10^6$，$k=0/1$，$\forall i \in [1,n-1],r_i < l_{i+1}$。

subtask 1（$15$ 分）：$q \le 2000$；

subtask 2（$25$ 分）：$k=0$；

subtask 3（$20$ 分）：$k=1,l_i = r_i$；

subtask 4（$40$ 分）：无。