Informatica Online Judge

  GSHS국의 산책 [1414 / 0586]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 16   Total Tried : 113


The Champion of this Problem (C++) : jjwdi0 - 0ms / 911byte
My Best Submission (C++) : N/A

[JOI15/16예선]

Background

GSHS국은 하나의 긴 직선으로 이루어진 국가이다.

대통령이 사는 관사의 위치를 좌표 0으로 지정하고, 관사의 왼쪽편을 음수, 오른쪽 편을 양수인 정수값으로 좌표를 지정했다.

GSHS국의 국민들은 모두 N명이고, 각 사람들은 서로 다른 짝수 좌표에서 생활한다.

i번째 국민이 사는 위치의 좌표는 A_i로 표시한다.

GSHS국을 다스리는 대통령 JK는 최근 국민들이 운동부족인 것을 걱정하여 모든 국민이 운동을 할 수 있도록 산책할 수 있도록 법을 재정했다.

GSHS국의 각 국민은 정해진 산책시간이 되면 모두 집에서 나와 왼쪽 또는 오른쪽으로 1초에 1칸의 속도로 산책을 시작한다.

모든 국민은 자기가 왼쪽으로 산책을 하는지 오른쪽으로 산책을 하는지 정해져 있다.

산책을 하다가 다른 국민과 한 좌표에서 만날 경우, 이 사람들은 그 자리에 멈춰서 서로 대화를 하기 시작한다.

또한 2명 이상이 멈춰서 대화를 하고 있는 좌표에 새로 진입한 국민이 있을 경우, 이 사람도 멈춰서 함께 대화를 하기 시작한다.

대화를 하기 위해서 멈춘 사람은 다시 움직이지 않는다. 그 만큼 GSHS국의 국민들은 서로 대화하기를 좋아한다.

GSHS국에는 Q명의 건강 관리인물이 존재한다.

대통령은 산책을 시작한 후 T초 후에 이 Q명이 각각 어느 위치에 존재하는지 알고 싶어한다.

이를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에는 n, T, Q의 값이 공백으로 구분되어 입력된다.

다음 줄부터 n줄에 걸쳐서 각 국민이 사는 좌표의 위치를 나타내는 정수(짝수) A_i와 각 국민이 산책을 하는 방향을 나타내는 정수 D_i가 공백으로 구분되어 입력된다.

D_i의 값이 1일 경우에는 오른쪽으로 산책하며, 2일 경우에는 왼쪽으로 산책하기 시작한다.

다음 줄부터 Q줄에 걸쳐서 각 주요 인물의 번호가 한 줄에 하나씩 주어진다.

[입력값의 정의역]
1 <= n <= 100,000
0 <= T <= 10^18
1 <= Q <= n
-10^18 <= A_i <= 10^18 ( A_i != 0 )
1 <= D_i <= 2
A_i < A_i+1
Q_i < Q_i+1

Output

각 Q명의 건강관리 인물의 위치를 한 줄에 하나씩 출력한다.

IO Example

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

출력
-6
-6
15

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]