JOI 국에는 동서로 충분히 긴 도로가 하나 있다. 왕궁이 이 도로 옆에 있고, 도로 위의 위치는 정수 \(A\)로 나타낸다. \(A = 0\)이면 왕궁의 위치이다. \(A > 0\)이면 왕궁에서 동쪽으로 \(A\)미터 간 위치이고, \(A < 0\)이면 왕궁에서 서쪽으로 \(-A\)미터 간 위치이다. 도로 옆에는 집이 \(N\)채 있고, 서쪽부터 \(1\)부터 \(N\)까지 번호가 붙어 있다. 국민도 \(N\)명이고 \(1\)부터 \(N\)까지 번호가 붙어 있다. 집 \(i\)에는 국민 \(i\)가 산다. 집 \(i\)의 위치는 \(0\)이 아닌 짝수 \(A_i\)로 나타내고, \(A_1, \ldots, A_N\)은 모두 다르다. 최근 국민의 운동 부족이 문제가 되었다. 건강이 걱정된 왕은 국민 모두에게 산책을 명했다. 명령이 떨어지면 모든 국민이 한꺼번에 동쪽 또는 서쪽으로 걷기 시작한다. 어느 쪽으로 시작할지는 사람마다 정해져 있다. 걸을 때는 \(1\)초에 \(1\)미터씩 움직인다. JOI 국 국민은 수다를 매우 좋아한다. 산책 중에 다른 국민을 만나면 그 자리에서 멈춰 이야기를 시작한다. 이미 멈춰 있는 국민을 만나도 마찬가지이다. 한 번 멈춘 국민은 다시 걷지 않는다. JOI 국에는 중요 인물이 \(Q\)명 있다. 왕은 명령을 내린 뒤 \(T\)초가 지났을 때 이 \(Q\)명의 위치를 알고 싶다. 명령을 내린 뒤 \(T\)초가 지났을 때 \(Q\)명의 위치를 구하라. |
입력은 다음 형식으로 주어진다.
\(N\) \(T\) \(Q\)
\(A_1\) \(D_1\)
\(\vdots\)
\(A_N\) \(D_N\)
\(X_1\)
\(\vdots\)
\(X_Q\)
- 입력은 \(1+N+Q\)줄이다.
- 첫째 줄에 정수 \(N\), \(T\), \(Q\)가 공백 하나로 구분되어 주어진다. 집이 \(N\)채 있고, 명령을 내린 뒤 \(T\)초가 지났을 때 \(Q\)명의 위치를 알고 싶다는 뜻이다.
- 이어지는 \(N\)줄 중 \(i\)번째 줄에 정수 \(A_i\), \(D_i\)가 공백 하나로 구분되어 주어진다. \(A_i\)는 집 \(i\)의 위치이고 \(0\)이 아닌 짝수이다. 모든 \(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\)가 주어진다. \(i\)번째 중요 인물이 집 \(X_i\)에 산다는 뜻이다. 모든 \(i\) (\(1 \le i \le Q-1\))에 대해 \(X_i < X_{i+1}\)이다.
- \(1 \le N \le 100000\)
- \(0 \le T \le 10^{18}\)
- \(1 \le Q \le 1000\)
- \(Q \le N\)
- \(-10^{18} \le A_i \le 10^{18}\)
- \(A_i\)는 \(0\)이 아닌 짝수이다.
- \(1 \le D_i \le 2\)
- \(1 \le X_i \le N\)
- 채점 입력 \(1\)에서는 \(N \le 100\), \(T \le 10000\)이다. 채점 입력 \(2\)에서는 \(N \le 5000\)이다. 채점 입력 \(3\)에서는 어떤 정수 \(M\) (\(1 \le M \le N-1\))이 있어, \(i \le M\)이면 \(D_i = 1\)이고 \(j \ge M+1\)이면 \(D_j = 2\)이다. 채점 입력 \(1, 2, 3\)에서 주어지는 정수의 절댓값은 \(10^9\)을 넘지 않는다. 채점 입력 \(4, 5\)에서는 주어지는 정수가 \(32\)비트 부호 있는 정수 범위에 들어가지 않을 수 있다.
- 입력되는 값은 모두 정수이다.
다음 형식으로 출력한다.
\(Q\)줄을 출력한다. \(i\)번째 줄(\(1 \le i \le Q\))에, 명령을 내린 뒤 \(T\)초가 지났을 때 \(i\)번째 중요 인물의 위치를 나타내는 정수를 출력한다. 이 값이 정수임은 문제 조건으로 보장된다.