방향을 바꾸는 자전거 거치대

문제

공유 자전거 대여소에는 자전거를 한 줄로 보관하는 긴 거치대가 있다. 거치대의 양 끝은 각각 왼쪽과 오른쪽으로 구분된다. 관리자는 두 끝 중 하나를 대여 쪽으로 지정하고, 반대쪽을 반납 쪽으로 지정한다. 처음에는 왼쪽이 대여 쪽이고 오른쪽이 반납 쪽이며, 거치대에는 자전거가 한 대도 없다. 자전거에는 양의 정수 번호가 붙어 있다. 같은 번호가 여러 번 기록될 수 있으며, 번호가 같더라도 기록에 등장한 자전거는 각각 별개의 한 대로 취급한다. 관리 기록은 발생한 순서대로 주어진다. 기록의 종류는 세 가지다. `1 x`는 번호가 x인 자전거 한 대를 현재 반납 쪽 끝에 추가하는 기록이다. 기존 자전거들의 상대적인 순서는 바뀌지 않는다. `2`는 현재 대여 쪽 끝에 있는 자전거 한 대를 꺼내는 기록이다. 꺼낸 자전거의 번호를 대여 결과로 남긴다. 거치대가 비어 있다면 아무것도 꺼내지 않고 대여 결과로 -1을 남긴다. 실패한 대여 기록도 다른 기록과 마찬가지로 처리한 뒤 다음 기록으로 넘어간다. `3`은 대여 쪽과 반납 쪽을 서로 바꾸는 기록이다. 이 기록은 어느 끝에서 자전거를 넣고 꺼낼지만 바꾸며, 거치대 안의 자전거를 실제로 이동시키지 않는다. 따라서 왼쪽부터 보았을 때 자전거가 놓인 순서는 그대로다. 거치대가 비어 있어도 방향 변경은 적용되며, 이후의 반납과 대여는 바뀐 방향을 따른다. 방향을 두 번 연속 바꾸면 원래 방향으로 돌아온다. 모든 기록은 입력에 주어진 순서대로 정확히 한 번씩 처리한다. 거치대에는 필요한 만큼 자전거를 보관할 수 있으므로 반납이 거절되는 경우는 없다. 각 대여 기록에서 남겨야 하는 결과를 순서대로 구하는 프로그램을 작성한다. 마지막에 남은 자전거의 번호나 개수는 출력하지 않는다.

입력

첫째 줄에 기록의 수 Q가 주어진다. (1 ≤ Q ≤ 40,000)
다음 Q개 줄에 기록이 하나씩 주어진다. 각 기록은 `1 x`, `2`, `3` 중 하나이며, x는 1 이상 9,999 이하의 정수다.
종류가 2인 기록이 적어도 하나 주어진다.

출력

종류가 2인 기록마다 대여 결과를 한 줄에 하나씩 출력한다. 자전거를 꺼냈다면 그 번호를, 거치대가 비어 있었다면 -1을 출력한다.

9
1 12
1 7
2
3
1 9
2
2
2
3

12
7
9
-1

7
3
2
1 5
1 5
3
2
2

-1
5
5

출처: Devin.KR 자체 제작