P12510 [集训队互测 2024] 游戏

小 $\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$。

### 样例 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$ 分）：无。