公园内有 $n$ 个人正在散步，随着天色渐晚，所有人准备回家离开公园。公园的结构是一个首尾相连的环形图，它共有 $m$ 个出口，为了方便叙述，我们将人从 $1\sim n$ 编号，将出口按逆时针顺序从 $1\sim m$ 编号。
公园总长 $L$ 米，我们令 $1$ 号出口所在的位置为 $0$ 米，则 编号为 $i(2\le i\le m)$ 的出口在 $1$ 号出口逆时针方向 $a_i$ 米的位置上，其中 $a_i$ 严格递增 ，即 $i(1\le i < m)$ 号出口与 $i+1$ 号出口相邻，由于公园是环形图，故 $m$ 号出口与 $1$ 号出口也相邻。每个出口还有一个通行限制 $l_i$，表示最多有 $l_i$ 个人能从 $i$ 号出口离开。
所有人回家时将按自己的朝向，可能是顺时针方向，也可能是逆时针方向不断前行，当他们走到一个还能离开的出口时，将从该出口离开公园。特别地，当两个人同时走到一个只能允许 $1$ 个人离开的出口时，编号小的那个人能从该出口离开，编号较大的人将继续前进。
现在给定 $n$ 个人所在的起始位置与他们的前进方向，请你求出每个人从哪个出口离开，若编号为 $i$ 的 人从 $k_i$ 号出口离开，你只需要给出 $i\times k_i$ 的异或和，即：
$$ (1\times k_1) xor (2\times k_2) xor\cdots xor (n\times k_n) $$
其中 $xor$ 是位异或运算。特别地若一个人最后无法离开，则他的 $k_i = 0$。

第一行三个正整数 $n, m, L$，意义见题目描述。
第二行 $m - 1$ 个正整数 $a_i(2\le i \le m)$ 表示出口位置。保证 $a_i$ 严格递增。
第三行 $m$ 个正整数 $l_i$ 表示出口的人数限制。
接下来 $n$ 行每行两个整数 $s_i,b_i(1 \le i \le n)$。若 $s_i$ 为 $0$ 表示编号为 $i$ 的人前进方向是逆时针方向，为 $1$ 表示是顺时针方向。 $b_i$ 表示编号为 $i$ 的人的起始位置为：离 $1$ 号出口逆时针方向 $b_i$ 米的位置。

仅一行一个整数表示答案。

3 2 5
2
2 1
0 1
1 3
0 4

3

3 2 5
2 
1 1
0 0 
0 2 
0 1

5

【样例 1 说明】
编号为 $1 ,2, 3$ 的人分别从 $2, 1, 1$ 号出口离开。
【样例 2 说明】
编号为 $1,2$ 的人分别从 $1 ,2$ 号出口离开，编号为 $3$ 的人无法离开公园。

【提示】

对于$ 12\% $的数据，保证$ n,m\leq 10 $ 
对于$ 32\% $的数据，保证$ n,m\leq 100, L \leq 1000 $
对于$ 52\% $的数据，保证$ n,m\leq 1000 $
另有$ 20\% $的数据，保证$ n,m \leq 10000 $且$ s_i = 0 $
对于$ 100\% $的数据，保证$ 1 \le n,m \le 2 \times 10^5 , 2 \le L \le 10^9 , 1\le a_i <L , 1\le l_i \le n, s_i\in\{0,1\} , 0\le b_i \lt L $