JOI 왕국의 산책

JOI 왕국에는 동서로 뻗은 충분히 긴 도로가 하나 있다. 도로변에 왕궁이 있고, 도로 위의 위치는 정수 $A$로 나타낸다. $A = 0$은 왕궁이 있는 지점이다. $A > 0$은 왕궁에서 동쪽으로 $A$미터 떨어진 지점이고, $A < 0$은 왕궁에서 서쪽으로 $-A$미터 떨어진 지점이다.

도로변에는 집이 $N$채 있고, 서쪽부터 차례로 $1$번부터 $N$번까지 번호가 붙어 있다. 국민도 $N$명이고 번호는 $1$번부터 $N$번까지다. 집 $i$에는 국민 $i$가 산다. 집 $i$의 위치는 $0$이 아닌 짝수 $A_i$이며, $A_1$부터 $A_N$까지는 모두 다르다.

최근 왕국에서는 국민의 운동 부족이 문제가 되었다. 국민의 건강을 걱정한 왕은 전원에게 산책을 하라고 명령했다. 명령이 떨어지면 모든 국민이 동시에 동쪽 또는 서쪽으로 걷기 시작한다. 어느 쪽으로 걷기 시작하는지는 국민마다 미리 정해져 있다. 걷는 속도는 모두 초속 $1$미터다.

왕국의 국민은 모두 수다를 좋아한다. 산책하다가 다른 국민과 마주치면 그 자리에 멈춰 서서 이야기를 시작한다. 이미 멈춰 있는 국민과 마주친 경우에도 마찬가지다. 한 번 멈춘 국민은 다시 걷지 않는다.

왕국에는 중요 인물이 $Q$명 있다. 왕은 명령을 내리고 $T$초가 지난 시점에 이 $Q$명이 각각 어디에 있는지 알고 싶다. 명령을 내리고 $T$초 후 중요 인물 $Q$명의 위치를 구하는 프로그램을 작성하시오.

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

첫째 줄에 정수 $N$, $T$, $Q$가 공백으로 구분되어 주어진다 ($1 \le N \le 100000$, $0 \le T \le 10^{18}$, $1 \le Q \le 1000$, $Q \le N$). 왕국에 집이 $N$채 있고, 왕이 명령을 내리고 $T$초 후 중요 인물 $Q$명의 위치를 알아야 한다는 뜻이다.

이어지는 $N$개의 줄 중 $i$번째 줄에는 정수 $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$이면 동쪽으로, $D_i = 2$이면 서쪽으로 걷기 시작한다.

이어지는 $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}$이다.

입력으로 주어지는 정수가 32비트 부호 있는 정수 범위를 벗어날 수 있다는 점에 주의하시오.

$Q$개의 줄을 출력한다.

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