JOI 왕국에는 동서로 뻗은 충분히 긴 $1$개의 도로가 있다. JOI 왕국의 왕궁이 도로변에 있으며, JOI 왕국에서 도로변의 위치는 정수 $A$로 나타낸다. $A = 0$일 때는 왕궁의 위치를 나타낸다. $A > 0$일 때는 왕궁에서 동쪽으로 $A$미터 나아간 위치를 나타낸다. $A < 0$일 때는 왕궁에서 서쪽으로 $-A$미터 나아간 위치를 나타낸다.

JOI 왕국의 도로변에는 $N$채의 집이 있으며, 집에는 서쪽에서부터 순서대로 $1$부터 $N$까지의 번호가 붙어 있다. JOI 왕국에는 $N$명의 국민이 있으며, 국민에게는 $1$부터 $N$까지의 번호가 붙어 있다. 집 $i$에는 국민 $i$가 살고 있다. 집 $i$의 위치는 $0$이 아닌 짝수 $A_i$로 나타낸다. $A_1, \dots, A_N$은 모두 서로 다르다.

JOI 왕국에서는 최근 국민들의 운동 부족이 문제가 되고 있다. 국민들의 건강이 걱정된 JOI 왕국의 왕은 모든 국민에게 산책을 하라는 명령을 내렸다. 왕이 명령을 내리면 모든 국민은 일제히 동쪽 또는 서쪽으로 걷기 시작한다. 각 국민이 어느 방향으로 걷기 시작할지는 국민마다 정해져 있다. 모든 국민은 걸을 때 $1$초당 $1$미터의 속도로 걷는다.

JOI 왕국의 국민들은 모두 수다를 무척 좋아한다. 산책 도중에 다른 국민을 만나면 그 자리에서 멈춰 서서 잡담을 시작해 버린다. 이미 멈춰 서 있는 국민을 만났을 경우에도 마찬가지이다. 한 번 멈춰 선 국민은 다시 걷기 시작하지 않는다.

JOI 왕국에는 $Q$명의 중요 인물이 있다. JOI 왕국의 왕은 명령이 내려진 지 $T$초 후의 $Q$명의 중요 인물의 위치를 파악해 두고 싶어 한다. 명령이 내려진 지 $T$초 후의 $Q$명의 중요 인물의 위치를 구하는 프로그램을 작성하시오.

입력

입력은 $1 + N + Q$줄로 이루어진다.

$1$번째 줄에는 $3$개의 정수 $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$)가 공백으로 구분되어 적혀 있다. 이는 JOI 왕국에 집이 $N$채 있으며, 왕이 명령을 내린 지 $T$초 후의 $Q$명의 중요 인물의 위치를 파악해 두고 싶어 함을 나타낸다.

이어지는 $N$개의 줄 중 $i$번째 줄에는 $2$개의 정수 $A_i, D_i$($-10^{18} \le A_i \le 10^{18}$, $A_i$는 $0$이 아닌 짝수, $1 \le D_i \le 2$)가 공백으로 구분되어 적혀 있다. $A_i$는 집 $i$의 위치를 나타내는 짝수이다. 모든 $i$($1 \le i \le N - 1$)에 대하여 $A_i < A_{i+1}$을 만족한다. $D_i$는 명령이 내려진 후 국민 $i$가 걷기 시작하는 방향을 나타낸다. $D_i = 1$일 때는 국민 $i$가 동쪽으로 걷기 시작한다. $D_i = 2$일 때는 국민 $i$가 서쪽으로 걷기 시작한다.

이어지는 $Q$개의 줄 중 $i$번째 줄에는 정수 $X_i$($1 \le X_i \le N$)가 적혀 있다. 이는 $i$번째 중요 인물이 집 $X_i$에 살고 있음을 나타낸다. 모든 $i$($1 \le i \le Q - 1$)에 대하여 $X_i < X_{i+1}$을 만족한다.

주어지는 $5$개의 입력 데이터 중 입력 $1$에서는 $N \le 100, T \le 10000$을 만족한다. 또한 입력 $2$에서는 $N \le 5000$을 만족한다. 또한 입력 $3$에서는 어떤 정수 $M$($1 \le M \le N - 1$)이 존재하여 모든 $i$($1 \le i \le M$)에 대하여 $D_i = 1$, 모든 $j$($M + 1 \le j \le N$)에 대하여 $D_j = 2$를 만족한다. 또한 입력 $1, 2, 3$에서는 입력으로 주어지는 정수의 절댓값이 $1000000000 (= 10^9)$을 넘지 않는다. 입력 $4, 5$에서는 주어지는 정수가 $32$비트 부호 있는 정수의 범위에 들어가지 않을 수 있음에 주의하라.

출력

출력은 $Q$줄로 이루어진다.

$i$번째 줄($1 \le i \le Q$)에는 왕이 명령을 내린 지 $T$초 후의 $i$번째 중요 인물의 위치를 나타내는 정수를 출력한다. 이 값이 정수임은 문제의 조건에 의해 보장된다.

예제

입력 1

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

출력 1

-6
-6
15

입력 2

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

출력 2

-82
-16
-13
-13
0