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

자동차들이 동시에 교차로를 통과하면 충돌할 수 있기 때문에, 효율적인 도로 교통 흐름을 위해서는 자동차끼리의 충돌을 방지할 수 있도록 자동차가 적절히 멈춰 있도록 하되, 너무 오래 멈춰 있지 않도록 소프트웨어를 적절하게 작성해야 한다. 이 문제에서 각 도로의 맨 앞에 있는 자동차는 자신을 기준으로 오른쪽에 위치한 도로에 차량이 있으면 1초 동안 출발하지 않고, 차량이 없으면 즉시 교차로를 통과한다. 정확한 설명을 위해 아래와 같은 상황을 생각하여 보자.

1번 차량이 C 위치에, 2번 차량이 B 위치에 있다. 두 차량이 동시에 출발하게 되면 왼쪽 그림과 같이 교차로 위에서 충돌할 우려가 있다. 1번 차량을 기준으로 오른쪽에 있는 도로인 B 위치의 도로에 차량이 있기 때문에, 1번 차량은 1초간 출발하지 않고, 2번 차량은 교차로를 통과한다. A 위치에 있는 차량의 오른쪽에 있는 도로는 D 위치의 도로이고, B 위치에 있는 차량의 오른쪽에 있는 도로는 A 위치의 도로이고, C 위치에 있는 차량의 오른쪽에 있는 도로는 B 위치의 도로이고, D 위치에 있는 차량의 오른쪽에 있는 도로는 C 위치의 도로이다. 위와 같이 1번 차량이 다른 차량이 지나갈 때까지 대기하는 동안 새로운 차량이 C 위치에 계속 진입할 수 있다. 차선이 하나밖에 없기 때문에, 맨 앞에 있는 차량이 지나가기 전까지는 해당 위치의 차선에 적체된 차량이 계속 늘어날 수 있다. 예를 들어 위의 상황에서 1초 뒤에 3번 차량이 B번 위치에, 4번 차량이 C번 위치에 진입할 경우, 아래와 같이 C번 위치에 1번 차량과 4번 차량이 대기하게 된다.

안전을 위해 각 위치마다 1초에 한 대씩만 교차로를 통과할 수 있다. 위의 그림과 같이 하나의 차선에 1번 차량과 4번 차량이 서 있고 이후에 차량이 새로 진입하지 않는다면, 1초 뒤에 1번 차량이 교차로를 통과하고, 다시 1초 뒤에 (즉 전체적으로 2초 뒤에) 2번 차량이 교차로를 통과할 것이다. A, B, C, D 위치에 동시에 차량이 한 대 이상씩 있다면, 교착 상태에 빠져 어떤 차량도 교차로를 통과할 수 없게 된다. 앞으로 $N$대의 차량이 교차로를 통과하기 위해 A, B, C, D 위치에 진입할 것이다. $i$ ($1 \le i \le N$)번 차량은 $t_i$초 때에 $w_i$ 위치에 진입하여, 해당 차선에 있는 줄 맨 뒤에 있을 예정이다. 혼선을 방지하기 위해, 같은 시각에 각 위치에 진입할 수 있는 차량은 최대 한 대이다. 매초마다, 모든 차량이 진입한 직후, 각 위치의 맨 앞에 있는 차량은 오른쪽 차선에 차량이 없는지 확인한 뒤, 차량이 없다면 교차로를 통과한다. 각 차량이 교차로를 통과하는 시각이 언제인지 계산하는 프로그램을 작성하라. # 입력 첫 번째 줄에 $N$이 주어진다. 다음 $N$개의 줄 중 $i$ ($1 \le i \le N$)번째 줄에는 $t_i$와 $w_i$가 공백 하나를 사이로 두고 주어진다. * $2 \le N \le 200\,000$ * 모든 $i$ ($1 \le i \le N$)에 대해: - $0 \le t_i \le 10^9$ - $w_i$는 A, B, C, D 중 하나이다. - $t_1 \le t_2 \le \cdots \le t_N$ - $i \neq j$이고 $t_i = t_j$이면, $w_i \neq w_j$이다. # 출력 $N$개의 줄을 출력한다. 이 중 $i$ ($1 \le i \le N$)번째 줄은 $i$번 차량이 도로를 통과한다면 교차로를 통과하는 시각, 교차로를 통과하지 않는다면 `-1`이어야 한다. # 서브태스크 | 번호 | 배점 | 제한 | | ---- | ---- | --------- | | 1 | 8 | $N = 2$ | | 2 | 30 | 모든 $i$ ($1 \le i \le N$)에 대해 $w_i$는 A, B 중 하나이다. | | 3 | 62 | 추가 제약 조건 없음. | # 노트 예제 3번의 경우 다음과 같이 진행된다.