아직 계정이 없으신가요? 회원가입

[인증평가(3차) 기출] 교차로
난이도
참가자 수
11
제출 수
43
정답률
35.71%
지원 언어

제한시간 : C/C++(2초), Java/JS/Python(3초)| 메모리 제한 : 1024MB


자율주행차가 아래와 같은 교차로를 통과하는 상황을 생각하여 보자. 이 문제에서 다루는 교차로에서는 직진만 가능하기 때문에, 아래 그림과 같은 네 가지 방법으로만 교차로를 통과할 수 있다.



자동차들이 동시에 교차로를 통과하면 충돌할 수 있기 때문에, 효율적인 도로 교통 흐름을 위해서는 자동차끼리의 충돌을 방지할 수 있도록 자동차가 적절히 멈춰 있도록 하되, 너무 오래 멈춰 있지 않도록 소프트웨어를 적절하게 작성해야 한다.

이 문제에서 각 도로의 맨 앞에 있는 자동차는 자신을 기준으로 오른쪽에 위치한 도로에 차량이 있으면 1초 동안 출발하지 않고, 차량이 없으면 즉시 교차로를 통과한다. A 위치에 있는 차량의 오른쪽에 있는 도로는 D 위치의 도로이고, B 위치에 있는 차량의 오른쪽에 있는 도로는 A 위치의 도로이고, C 위치에 있는 차량의 오른쪽에 있는 도로는 B 위치의 도로이고, D 위치에 있는 차량의 오른쪽에 있는 도로는 C 위치의 도로이다. 정확한 설명을 위해 아래와 같은 상황을 생각하여 보자.



1번 차량이 C 위치에, 2번 차량이 B 위치에 있다. 두 차량이 동시에 출발하게 되면 왼쪽 그림과 같이 교차로 위에서 충돌할 우려가 있다. 1번 차량을 기준으로 오른쪽에 있는 도로인 B 위치의 도로에 차량이 있기 때문에, 1번 차량은 1초간 출발하지 않고, 2번 차량은 교차로를 통과한다.

위와 같이 1번 차량이 다른 차량이 지나갈 때까지 대기하는 동안 새로운 차량이 C 위치에 계속 진입할 수 있다. 차선이 하나밖에 없기 때문에, 맨 앞에 있는 차량이 지나가기 전까지는 해당 위치의 차선에 적체된 차량이 계속 늘어날 수 있다. 예를 들어 위의 상황에서 1초 뒤에 3번 차량이 B번 위치에, 4번 차량이 C번 위치에 진입할 경우, 아래와 같이 C번 위치에 1번 차량과 4번 차량이 대기하게 된다.



안전을 위해 각 위치마다 1초에 한 대씩만 교차로를 통과할 수 있다. 위의 그림과 같이 하나의 차선에 1번 차량과 4번 차량이 서 있고 이후에 차량이 새로 진입하지 않는다면, 1초 뒤에 1번 차량이 교차로를 통과하고, 다시 1초 뒤에 (전체적으로 2초 뒤에) 4번 차량이 교차로를 통과할 것이다.

A, B, C, D 위치에 동시에 차량이 한 대 이상씩 있다면, 교착 상태에 빠져 어떤 차량도 교차로를 통과할 수 없게 된다.

앞으로 N대의 차량이 교차로를 통과하기 위해 A, B, C, D 위치에 진입할 것이다. i (1 ≤ i ≤ N)번 차량은 ti초 때에 wi 위치에 진입하여, 해당 차선에 있는 줄 맨 뒤에 있을 예정이다. 혼선을 방지하기 위해, 같은 시각에 각 위치에 진입할 수 있는 차량은 최대 한 대이다.

매초마다 모든 차량이 진입한 직후, 각 위치의 맨 앞에 있는 차량은 오른쪽 위치에 차량이 없는지 확인한 뒤, 차량이 없다면 교차로를 통과한다.

각 차량이 교차로를 통과하는 시각이 언제인지 계산하는 프로그램을 작성하라.


제약조건
  • 2 ≤ N ≤ 200,000
  • 모든 i(1 ≤ i ≤ N)에 대해, 0 ≤ ti ≤ 109이고, wi는 A, B, C, D 중 하나이다
  • t1 ≤ t2 ≤ … ≤ tN
  • i ≠ j 이고 ti = tj이면, wi ≠ wj이다


입력형식
첫 번째 줄에 N이 주어진다.
다음 N개의 줄 중 i (1 ≤ i ≤ N)번째 줄에는 ti와 wi가 공백 하나를 사이로 두고 주어진다.


출력형식
첫 번째 줄에 N개의 정수를 공백 하나씩을 사이로 두고 출력한다.
이 중 i (1 ≤ i ≤ N)번째 정수는 i번 차량이 도로를 통과한다면 교차로를 통과하는 시각, 교차로를 통과하지 않는다면 -1이어야 한다.


입력예제1
2
10 A
10 B


출력예제1
10
11


입력예제2
6
0 A
0 C
1 A
1 B
1 C
1 D


출력예제2
0
0
-1
-1
-1
-1


입력예제3
6
0 A
0 B
0 C
2 D
2 C
4 B


출력예제3
0
1
2
4
3
4


예제3 설명