JOI 국의 산책 사정

문제

JOI 국에는 동서로 뻗은 충분히 긴 도로가 하나 있다. 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}$, ..., $A_{N}$ 은 모두 다르다.

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

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

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

입력

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

1 번째 줄에는 세 정수 N, T, Q (1 ≦ N ≦ 100000 (= $10^{5}$), 0 ≦ T ≦ $10^{18}$, 1 ≦ Q ≦ 1000, 1 ≦ Q ≦ N) 가 공백으로 구분되어 쓰여 있다. 이는 JOI 국에 집이 N 채 있고, 왕이 명령을 내린 지 T 초 후의 Q 명의 중요 인물의 위치를 파악해 두고 싶음을 나타낸다.

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

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

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

출력

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

i 번째 줄 (1 ≦ i ≦ 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