[CSP-S2019 江西] 散步

JXCSP-S T4

公园内有 $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) \operatorname{xor} (2\times k_2) \operatorname{xor}\cdots \operatorname{xor} (n\times k_n) $$ 其中 $\operatorname{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, L \le 10$； 对于 $32\%$ 的数据：$n, m \le 100$，$L \le 1000$； 对于 $52\%$ 的数据：$n, m \le 1000$； 另有 $20\%$ 的数据：$n, m \le 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<L$。