창구 안내판 바꾸기

문제

어느 은행에는 1번 창구와 2번 창구가 있고, 각 창구 앞에는 손님이 기다리는 줄이 하나씩 있다. 은행이 문을 열었을 때 두 줄은 모두 비어 있다. 손님은 은행에 도착한 순서대로 1번부터 시작하는 접수 번호를 받는다. 접수 번호는 두 창구가 함께 사용하는 번호이므로, 어느 줄에 들어가든 새 손님이 올 때마다 다음 번호를 받는다. 은행의 운영 기록에는 다섯 종류의 사건이 적혀 있다. 사건 1은 새 손님 한 명이 접수 번호를 받고 1번 창구의 줄 맨 뒤에 서는 사건이다. 사건 2는 새 손님 한 명이 접수 번호를 받고 2번 창구의 줄 맨 뒤에 서는 사건이다. 사건 3은 1번 창구가 자기 줄의 맨 앞 손님 한 명을 불러 상담을 시작하는 사건이며, 사건 4는 2번 창구가 같은 방식으로 손님 한 명을 부르는 사건이다. 상담을 시작한 손님은 즉시 줄에서 빠진다. 해당 줄이 비어 있다면 아무도 부르지 않는다. 사건 5는 직원이 두 대기 구역의 창구 안내판을 맞바꾸는 사건이다. 이때 지금까지 1번 창구에서 기다리던 줄 전체는 2번 창구의 줄이 되고, 2번 창구에서 기다리던 줄 전체는 1번 창구의 줄이 된다. 각 줄 안에서 손님들이 기다리는 순서는 그대로 유지된다. 한쪽 줄이나 양쪽 줄이 비어 있어도 안내판은 똑같이 바꾼다. 이미 상담을 시작한 손님은 이 사건의 영향을 받지 않는다. 사건은 기록에 적힌 순서대로 하나씩 처리한다. 모든 사건은 앞 사건의 처리가 끝난 뒤에 발생하므로 동시에 도착한 손님이나 호출 순서의 동점은 없다. 사건 3 또는 사건 4가 발생할 때마다 실제로 부른 손님의 접수 번호를 기록한다. 줄이 비어 있어 부를 손님이 없었다면 대신 0을 기록한다. 주어진 운영 기록을 처리하여 이 기록값들을 순서대로 출력하는 프로그램을 작성한다. 손님의 도착이나 안내판 교환에 대해서는 아무 값도 출력하지 않는다.

입력

첫째 줄에 사건의 수 N이 정수로 주어진다. 1 ≤ N ≤ 100,000이다.
다음 N개의 줄에는 사건의 종류를 나타내는 정수 C가 하나씩 주어진다. 1 ≤ C ≤ 5이며 각 값의 의미는 지문과 같다.
사건 3 또는 사건 4가 적어도 한 번 주어진다. 접수 번호는 사건 1 또는 사건 2가 발생할 때만 하나씩 증가한다.

출력

사건 3 또는 사건 4마다 부른 손님의 접수 번호를 한 줄에 하나씩 출력한다. 해당 창구의 줄이 비어 있었다면 0을 출력한다. 출력 순서는 사건이 발생한 순서와 같아야 한다.

10
1
2
1
5
3
4
2
4
4
3

2
1
3
4
0

7
3
4
5
2
5
3
4

0
0
1
0

출처: Devin.KR 자체 제작