Problem Description

JOI Kingdom has a single, sufficiently long road running east-west. The palace of JOI Kingdom is located along this road, and the position along the road in JOI Kingdom is represented by an integer \( A \). When \( A = 0 \), it represents the position of the palace. When \( A > 0 \), it represents the position \( A \) meters east of the palace. When \( A < 0 \), it represents the position \( -A \) meters west of the palace.

There are \( N \) houses along the road in JOI Kingdom, numbered from 1 to \( N \) from west to east. There are \( N \) citizens in JOI Kingdom, also 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, \ldots, A_N \) are distinct.

Recently, the lack of exercise among the citizens has become a concern. Worried about the health of his citizens, the king of JOI Kingdom has ordered everyone to go for a walk. Upon the king's order, all citizens start walking either eastward or westward simultaneously. Each citizen has a predetermined direction to start walking. All citizens walk at a speed of 1 meter per second.

The citizens of JOI Kingdom love to chat. If they meet another citizen while walking, they will stop and start chatting. This also applies if they meet a citizen who has already stopped. Once a citizen stops, they will not start walking again.

There are \( Q \) important figures in JOI Kingdom. The king wants to know the positions of these \( Q \) important figures \( T \) seconds after the order is given. Write a program to determine the positions of the \( Q \) important figures \( T \) seconds after the order is given.

Input Format

The input consists of \( 1 + N + Q \) lines.

The first line contains three integers \( N \), \( T \), and \( Q \) (\( 1 \leq N \leq 100,000 (= 10^5) \), \( 0 \leq T \leq 10^{18} \), \( 1 \leq Q \leq 1,000 \), \( 1 \leq Q \leq N \)) separated by spaces. This indicates that there are \( N \) houses in JOI Kingdom, and the king wants to know the positions of \( Q \) important figures \( T \) seconds after the order is given.

The next \( N \) lines contain two integers \( A_i \) and \( D_i \) (\( -10^{18} \leq A_i \leq 10^{18} \), \( A_i \) is a non-zero even number, \( 1 \leq D_i \leq 2 \)) separated by spaces. \( A_i \) is the position of house \( i \). For all \( i \) (\( 1 \leq i \leq N - 1 \)), \( A_i < A_{i + 1} \) holds. \( D_i \) indicates the direction in which citizen \( i \) starts walking after the order. \( D_i = 1 \) means citizen \( i \) starts walking eastward, and \( D_i = 2 \) means citizen \( i \) starts walking westward.

The next \( Q \) lines contain an integer \( X_i \) (\( 1 \leq X_i \leq N \)). This indicates that the \( i \)-th important figure lives in house \( X_i \). For all \( i \) (\( 1 \leq i \leq Q - 1 \)), \( X_i < X_{i + 1} \) holds.

Among the five input data sets provided, input 1 satisfies \( N \leq 100 \) and \( T \leq 10,000 \). Input 2 satisfies \( N \leq 5,000 \). Input 3 has an integer \( M \) (\( 1 \leq M \leq N - 1 \)) such that for all \( i \) (\( 1 \leq i \leq M \)), \( D_i = 1 \) and for all \( j \) (\( M + 1 \leq j \leq N \)), \( D_j = 2 \). For inputs 1, 2, and 3, the absolute values of the given integers do not exceed \( 1,000,000,000 (= 10^9) \). For inputs 4 and 5, note that the given integers may not fit within the range of a 32-bit signed integer.

Output Format

The output consists of \( Q \) lines.

The \( i \)-th line (\( 1 \leq i \leq Q \)) should contain the integer representing the position of the \( i \)-th important figure \( T \) seconds after the king's order. This value is guaranteed to be an integer based on the problem's conditions.

Sample Input and Output

Sample Input #1

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

Sample Output #1

-6
-6
15

Sample Input #2

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

Sample Output #2

-82
-16
-13
-13
0

见题面 Input 部分

见题面 Output 部分