Problem Description

There are $n$ people strolling in the park, and as it gets darker, everyone is preparing to leave the park and go home. The structure of the park is a circular graph with a total of $m$ exits. For convenience, we number the people from $1$ to $n$ and the exits in a counterclockwise order from $1$ to $m$.

The total length of the park is $L$ meters. We designate the position of the exit numbered $1$ as $0$ meters. Then, the exit numbered $i$ ($2 \le i \le m$) is located $a_i$ meters counterclockwise from the exit numbered $1$, where $a_i$ is strictly increasing. That is, exit $i$ ($1 \le i < m$) is adjacent to exit $i+1$, and since the park is a circular graph, exit $m$ is also adjacent to exit $1$. Each exit has a passage limit $l_i$, indicating that at most $l_i$ people can leave through exit $i$.

When everyone goes home, they will continue to move in their direction, which could be clockwise or counterclockwise. When they reach an exit that still allows people to leave, they will exit the park through that exit. Specifically, if two people simultaneously reach an exit that can only accommodate one person, the person with the smaller number will exit through that exit, and the person with the larger number will continue to move.

Given the initial positions and directions of $n$ people, you need to determine through which exit each person leaves. If the person numbered $i$ leaves through exit $k_i$, you only need to provide 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. If a person cannot leave, their $k_i = 0$.

Input Format

The first line contains three positive integers $n, m, L$, as described in the problem.

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

The third line contains $m$ positive integers $l_i$ representing the passage limits of the exits.

The next $n$ lines each contain two integers $s_i, b_i$ ($1 \le i \le n$). If $s_i$ is $0$, it indicates that the person numbered $i$ moves in the counterclockwise direction; if $s_i$ is $1$, it indicates the clockwise direction. $b_i$ represents the initial position of the person numbered $i$: $b_i$ meters counterclockwise from the exit numbered $1$.

Output Format

Output a single integer representing the answer.

Sample Input and Output

Input Sample #1

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

Output Sample #1

3

Input Sample #2

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

Output Sample #2

5

Notes

Sample 1 Explanation

The people numbered $1, 2, 3$ leave through exits $2, 1, 1$ respectively.

Sample 2 Explanation

The people numbered $1, 2$ leave through exits $1, 2$ respectively, and the person numbered $3$ cannot leave the park.

Data Constraints

For $12\%$ of the data: $n, m, L \le 10$;

For $32\%$ of the data: $n, m \le 100$, $L \le 1000$;

For $52\%$ of the data: $n, m \le 1000$;

For an additional $20\%$ of the data: $n, m \le 10000$, all $s_i = 0$;

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

见题面 Input 部分

见题面 Output 部分