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

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

样例输出 1

16

样例 1 解释

对于 $ x=8 $ 的询问。

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

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

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

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

样例输入 2

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

样例输出 2

468

样例 3，4

见下发文件，分别满足子任务 2，4 的性质。

数据范围

对于所有数据，保证：$ 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 分）：无。