바뀌는 주차 통로

문제

작은 주차장에는 자동차를 한 줄로 세우는 긴 통로가 있다. 통로의 양쪽 끝에는 문이 하나씩 있으며, 한쪽 문은 입구로, 반대쪽 문은 출구로 사용한다. 처음에는 왼쪽 문이 출구이고 오른쪽 문이 입구이며, 통로에는 자동차가 없다. 통로의 길이는 충분하므로 자동차가 들어오지 못하는 일은 없다. 관리자는 시간순으로 기록된 명령을 처리한다. 명령은 정수 1, 2, 3 중 하나이며, 한 명령의 처리를 모두 마친 뒤 다음 명령을 처리한다. 명령 1은 자동차 한 대가 현재 입구로 들어오는 것이다. 새 자동차는 입구에 가장 가까운 자리에 서며, 이미 주차된 자동차들의 상대적인 순서는 바뀌지 않는다. 자동차의 번호는 들어온 순서대로 1번, 2번, 3번처럼 붙인다. 출차하거나 문 역할을 바꾸어도 이미 사용한 번호를 다시 사용하지 않는다. 명령 2는 두 문의 역할을 서로 바꾸는 것이다. 지금까지 입구였던 문이 출구가 되고, 출구였던 문이 입구가 된다. 이때 자동차가 이동하거나 자동차들의 순서가 바뀌는 것은 아니다. 통로가 비어 있어도 문의 역할은 바뀌며, 바뀐 역할은 다음 명령에도 그대로 적용된다. 따라서 역할을 연속으로 두 번 바꾸면 두 문은 원래 역할로 돌아온다. 명령 3은 현재 출구에 가장 가까운 자동차 한 대를 내보내고 그 번호를 기록하는 것이다. 통로가 비어 있다면 자동차를 내보내지 않고 0을 기록한다. 빈 통로에서 출차를 시도해도 다음에 들어올 자동차의 번호에는 영향을 주지 않는다. 자동차는 출구 쪽 끝에서만 나갈 수 있으므로 여러 자동차 중 하나를 선택하거나 번호를 기준으로 순서를 정할 필요는 없다. 모든 명령을 순서대로 처리했을 때 명령 3마다 기록되는 값을 구한다. 명령 3이 한 번도 주어지지 않았다면 기록할 값이 없다는 뜻으로 -1을 출력한다.

입력

첫째 줄에 명령의 개수 N이 주어진다. N은 1 이상 100,000 이하의 정수다.
다음 N개의 줄에는 명령을 나타내는 정수 하나가 주어진다. 각 정수는 1, 2, 3 중 하나다. 명령 1로 들어오는 자동차의 번호는 입력에 따로 주어지지 않는다.

출력

명령 3이 주어질 때마다 기록한 정수를 명령의 처리 순서대로 한 줄에 하나씩 출력한다. 출차할 자동차가 없었던 명령의 기록은 0이다. 명령 3이 한 번도 주어지지 않았다면 -1을 한 줄에 출력한다.

9
1
1
2
1
3
2
3
3
3

2
3
1
0

7
3
2
1
2
1
3
3

0
1
2

5
1
2
1
2
1

-1

출처: Devin.KR 자체 제작