Description

There are $n$ people taking a walk in a park. As it gets late, everyone is ready to go home and leave the park. The park is a circular graph (a ring) with $m$ exits. For convenience, we number the people from $1$ to $n$, and number the exits from $1$ to $m$ in counterclockwise order.

The total length of the park is $L$ meters. We define the position of exit $1$ as $0$ meters. Then for exit $i\ (2\le i\le m)$, it is located $a_i$ meters counterclockwise from exit $1$. The sequence $a_i$ is strictly increasing, so exits $i\ (1\le i < m)$ and $i+1$ are adjacent. Since the park is a ring, exit $m$ and exit $1$ are also adjacent. Each exit also has a capacity limit $l_i$, meaning that at most $l_i$ people can leave through exit $i$.

When going home, each person will keep moving in their own direction, either clockwise or counterclockwise. When they reach an exit that still allows someone to leave, they will leave the park through that exit. In particular, if two people arrive at an exit that can allow only $1$ person to leave at the same time, the person with the smaller index leaves through that exit, and the person with the larger index continues moving.

Now you are given the initial position and moving direction of each of the $n$ people. Please determine which exit each person leaves from. If person $i$ leaves from exit $k_i$, you only need to output the XOR sum of $i\times k_i$, that is:

$$(1\times k_1) \operatorname{xor} (2\times k_2) \operatorname{xor}\cdots \operatorname{xor} (n\times k_n)$$

where $\operatorname{xor}$ is the bitwise XOR operation. In particular, if a person cannot leave in the end, then $k_i = 0$.

Input Format

The first line contains three positive integers $n, m, L$, as described above.

The second line contains $m - 1$ positive integers $a_i\ (2\le i \le m)$, representing the exit positions. It is guaranteed that $a_i$ is strictly increasing.

The third line contains $m$ positive integers $l_i$, representing the capacity limit of each exit.

The next $n$ lines each contain two integers $s_i, b_i\ (1 \le i \le n)$. If $s_i$ is $0$, it means person $i$ moves counterclockwise; if $s_i$ is $1$, it means person $i$ moves clockwise. $b_i$ means the starting position of person $i$ is the point $b_i$ meters counterclockwise from exit $1$.

Output Format

Output one integer in a single line, representing the answer.

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

Hint

Explanation of Sample 1

People $1, 2, 3$ leave through exits $2, 1, 1$, respectively.

Explanation of Sample 2

People $1, 2$ leave through exits $1, 2$, respectively, and person $3$ cannot leave the park.

Constraints

For $12\%$ of the testdata: $n, m, L \le 10$.

For $32\%$ of the testdata: $n, m \le 100$, $L \le 1000$.

For $52\%$ of the testdata: $n, m \le 1000$.

For another $20\%$ of the testdata: $n, m \le 10000$, and all $s_i = 0$.

For $100\%$ of the testdata: $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$.

Translated by ChatGPT 5