교차로
시간 제한2초메모리 제한1024 MB
네 방향 교차로에 N대의 차가 도착할 때, 주도로 방향 a와 b를 바탕으로 양보 규칙을 적용해 각 차가 교차로를 통과하는 시각을 구합니다.
문제
플랫랜드의 수도 뉴플레츠시티는 교통사고를 줄이고자 한 현명한 시장이 건설했습니다. 도시의 모든 교차로는 두 도로가 직각으로 만나 이루어집니다. 플레츠스테이트 빌딩 전망대에서 내려다보면 도시는 도로로 둘러싸인 같은 크기의 정사각형이 셀 수 없이 늘어선 모양이고, 각 정사각형의 네 모서리에 교차로가 있습니다. 모든 교차로는 네 방향으로 갈라지므로 교통 규칙이 단순하고 명확합니다.
어느 날 뉴플레츠시티에 사는 젊은 세레자는 운전면허를 따기로 하고 운전학원에 등록했습니다. 첫 수업에서는 서로 등급이 다른 도로의 교차로 통행 규칙을 배웠습니다. 규칙은 세 가지입니다.
- 등급이 다른 도로의 교차로에서 보조도로를 달리는 운전자는 주도로로 접근하는 차량에 양보해야 합니다.
- 교차로에서 주도로가 방향을 바꾸면, 주도로를 달리는 운전자끼리는 등급이 같은 도로의 교차로 규칙을 따릅니다.
- 등급이 같은 도로의 교차로에서 운전자는 오른쪽에서 접근하는 차량에 양보해야 합니다.
선생님은 세레자에게 문제를 여러 개 냈습니다. 세레자가 사는 뉴플레츠시티의 교차로는 모두 네 방향으로 갈라지므로, 각 문제는 N대의 차량이 교차로를 지나는 순서를 묻습니다. 차량은 네 방향에서 정해진 시각에 접근합니다. 방향은 시계 방향으로 1, 2, 3, 4번입니다. 단위 시간마다 각 방향에서 최대 한 대의 차량이 도착합니다. 모든 운전자는 교통 규칙을 어기지 않고 앞차를 추월하지 않을 만큼 예의 바릅니다. 모든 차량은 직진하려고 합니다. 방향 a와 b에서 접근하는 차량은 주도로에 있고, 나머지 차량은 보조도로에 있습니다.
차량은 다음 두 조건을 모두 만족할 때에만 교차로를 지납니다.
- 교차로로 향하는 대기열에서 자기 앞에 서 있는 차량이 없다.
- 양보해야 할 차량이 남아 있지 않다.
대기열 맨 앞의 두 차량이 서로 양보할 필요가 없다면, 두 차량은 동시에 교차로를 지납니다.
세레자가 모든 문제를 풀 수 있도록 도와주세요.
입력
첫째 줄에 차량의 수 N (1 \le N \le 100)이 주어집니다. 둘째 줄에는 주도로를 이루는 방향 a와 b (1 \le a,b \le 4, a \ne b)가 주어집니다.
이어지는 N개의 줄에는 각각 i번째 차량의 방향 d_i와 도착 시각 t_i (1 \le d_i \le 4, 1 \le t_i \le 100)가 주어집니다.
출력
N개의 정수를 한 줄에 하나씩 출력합니다. i번째 줄에는 i번째 차량이 교차로를 지나는 시각을 출력합니다.
차량은 입력에 나온 순서대로 번호가 매겨집니다.