Little A and Little B like to play games.

They play on a number line where items are placed at various positions. Initially, they have a parameter $k$, where it is guaranteed that $k=0$ or $k=1$.

Little A chooses a position $x$, which means Little B's position is $x+k$. The two players take turns picking up items, with Little A going first.

When it is a player's turn, they pick up the item currently remaining that is closest to their own position. If two items are at the same distance, they pick up the one with the smaller position.

The distance between positions $a$ and $b$ is defined as $|a-b|$.

After all items have been picked up, Little A wants to know the sum of the positions of the items they have collected.

Since they have plenty of time, they will play $q$ games. After each game, all items are restored to their original positions. For each game, Little A wants to know the sum of the positions of the items they collected, given their position $x$ and Little B's position $x+k$.

Input

The first line contains three integers $n, q, k$, representing the number of intervals containing items, the number of games, and the initial parameter.

The next $n$ lines each contain two integers $l_i, r_i$, indicating that there is an item at every position in the interval $[l_i, r_i]$.

The next $q$ lines each contain an integer $x$, representing Little A's parameter for that round, with Little B's parameter being $x+k$.

Output

Let $ans_i$ be the answer for the $i$-th query. Output a single integer representing $\oplus_{i=1}^{q} i \times ans_i$.

Examples

Input 1

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

Output 1

16

Note 1

For the query $x=8$:

The positions of the items Little A collected at the end are $8, 7, 5, 4$.

The positions of the items Little B collected at the end are $10, 11, 13$.

Therefore, the sum of the positions of the items Little A collected is $8+7+5+4 = 24$.

For the query $x=6$, the answer is $32$.

Input 2

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

Output 2

468

Note 3, 4

See the provided files, which satisfy the properties of subtasks 2 and 4, respectively.

Constraints

For all data, it is guaranteed that: $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$, and $\forall i \in [1,n-1], r_i < l_{i+1}$.

Subtask 1 (15 points): $q \le 2000$.

Subtask 2 (25 points): $k=0$.

Subtask 3 (20 points): $k=1, l_i = r_i$.

Subtask 4 (40 points): No additional constraints.