In JOI Kingdom, there is $1$ sufficiently long road running from east to west. The royal palace of JOI Kingdom is located along the road, and a position along the road in JOI Kingdom is represented by an integer $A$. When $A = 0$, it represents the position of the royal palace. When $A > 0$, it represents the position $A$ meters east of the royal palace. When $A < 0$, it represents the position $-A$ meters west of the royal palace.

There are $N$ houses along the road in JOI Kingdom, and the houses are numbered from $1$ to $N$ in order from west to east. There are $N$ citizens in JOI Kingdom, numbered from $1$ to $N$. Citizen $i$ lives in house $i$. The position of house $i$ is represented by a non-zero even integer $A_i$. All $A_1, \dots, A_N$ are distinct.

In JOI Kingdom, lack of exercise among the citizens has recently become a problem. Concerned about the health of the citizens, the King of JOI Kingdom issued an order for all citizens to take a walk. Once the King issues the order, all citizens simultaneously start walking either eastward or westward. Which direction each citizen starts walking is predetermined for each citizen. Every citizen walks at a speed of $1$ meter per $1$ second when walking.

All citizens of JOI Kingdom love chatting. If a citizen meets another citizen during the walk, they stop at that spot and start chatting. The same applies if a citizen meets another citizen who has already stopped. Once a citizen has stopped, they never start walking again.

There are $Q$ important people in JOI Kingdom. The King of JOI Kingdom wants to know the positions of the $Q$ important people $T$ seconds after the order is issued. Write a program to find the positions of the $Q$ important people $T$ seconds after the order is issued.

Input

The input consists of $1 + N + Q$ lines.

On the $1$-st line, $3$ integers $N, T, Q$ ($1 \le N \le 100000 (= 10^5), 0 \le T \le 10^{18}, 1 \le Q \le 1000, 1 \le Q \le N$) are written, separated by spaces. This indicates that there are $N$ houses in JOI Kingdom, and the King wants to know the positions of the $Q$ important people $T$ seconds after the order is issued.

On the $i$-th line of the following $N$ lines, $2$ integers $A_i, D_i$ ($-10^{18} \le A_i \le 10^{18}$, $A_i$ is a non-zero even integer, $1 \le D_i \le 2$) are written, separated by a space. $A_i$ is an even integer representing the position of house $i$. For all $i$ ($1 \le i \le N - 1$), $A_i < A_{i+1}$ holds. $D_i$ represents the direction in which citizen $i$ starts walking after the order is issued. When $D_i = 1$, citizen $i$ starts walking eastward. When $D_i = 2$, citizen $i$ starts walking westward.

On the $i$-th line of the following $Q$ lines, an integer $X_i$ ($1 \le X_i \le N$) is written. This indicates that the $i$-th important person lives in house $X_i$. For all $i$ ($1 \le i \le Q - 1$), $X_i < X_{i+1}$ holds.

Among the $5$ given input datasets, Input $1$ satisfies $N \le 100, T \le 10000$. Input $2$ satisfies $N \le 5000$. Input $3$ satisfies that there exists an integer $M$ ($1 \le M \le N - 1$) such that $D_i = 1$ for all $i$ ($1 \le i \le M$) and $D_j = 2$ for all $j$ ($M + 1 \le j \le N$). Furthermore, in Inputs $1, 2, 3$, the absolute values of the integers given in the input do not exceed $1000000000 (= 10^9)$. Note that in Inputs $4, 5$, the given integers may not fit within the range of a $32$-bit signed integer.

Output

The output consists of $Q$ lines.

On the $i$-th line ($1 \le i \le Q$), output an integer representing the position of the $i$-th important person $T$ seconds after the King issues the order. It is guaranteed by the conditions in the problem statement that this value is an integer.

Examples

Input 1

5 5 3
-8 1
-4 2
-2 2
4 2
10 1
1
3
5

Output 1

-6
-6
15

Input 2

7 18 5
-100 1
-56 2
-34 1
-30 1
-22 1
-4 2
18 2
1
3
4
5
7

Output 2

-82
-16
-13
-13
0