양쪽에서 꺼내는 반납 책

문제

도서관에서는 반납된 책을 긴 이동식 받침대 위에 한 줄로 놓는다. 받침대에는 양쪽 끝이 있으며, 담당 사서는 현재 바라보는 방향을 기준으로 왼쪽과 오른쪽을 구분한다. 처음에는 받침대가 비어 있다. 책마다 관리 번호가 붙어 있지만, 같은 종류의 책은 같은 관리 번호를 사용할 수 있으므로 번호가 같은 책이 여러 권 놓일 수도 있다. 사서가 남긴 작업 기록에는 다섯 종류의 작업이 있다. `1 x`는 관리 번호가 x인 책 한 권을 현재 왼쪽 끝에 놓는 작업이고, `2 x`는 그 책을 현재 오른쪽 끝에 놓는 작업이다. `3`은 현재 왼쪽 끝의 책 한 권을 꺼내는 작업이고, `4`는 현재 오른쪽 끝의 책 한 권을 꺼내는 작업이다. 책을 꺼내는 작업에서는 꺼낸 책의 관리 번호를 기록한다. 받침대가 비어 있으면 책을 꺼내지 않고 대신 -1을 기록한다. 나머지 작업 `5`는 사서가 받침대의 반대편으로 이동하는 작업이다. 이 작업을 수행하면 현재 왼쪽과 오른쪽이 서로 바뀐다. 예를 들어 왼쪽부터 관리 번호가 12, 8, 31인 상태에서 `5`를 수행하면, 새로운 방향에서는 왼쪽부터 31, 8, 12로 보인다. 그 뒤에 수행하는 모든 작업은 바뀐 방향을 기준으로 한다. 빈 받침대에서도 반대편으로 이동할 수 있다. 작업은 입력에 주어진 순서대로 모두 수행한다. 한 권을 놓는 작업은 기존 책들의 상대적인 순서를 바꾸지 않으며, 책을 꺼내는 작업은 해당 끝의 한 권만 제거한다. 작업 기록을 보고 책을 꺼낼 때마다 남긴 값을 순서대로 구하는 프로그램을 작성한다. 책을 꺼내는 작업이 한 번도 없다면 정해진 문자열을 출력한다.

입력

첫째 줄에 작업 수 N이 주어진다. N은 1 이상 40,000 이하의 정수다.
다음 N개 줄에 작업이 한 줄에 하나씩 주어진다. 각 줄은 `1 x`, `2 x`, `3`, `4`, `5` 중 하나다. x는 1 이상 9,999 이하의 정수다. 같은 x가 여러 번 주어질 수 있다.

출력

종류가 3 또는 4인 작업마다 꺼낸 책의 관리 번호를 한 줄에 하나씩 출력한다. 해당 작업 직전에 받침대가 비어 있었다면 -1을 출력한다. 종류가 3 또는 4인 작업이 하나도 없다면 EMPTY를 한 줄에 출력한다.

9
1 12
2 8
1 31
5
3
2 7
4
3
4

8
7
12
31

5
3
5
4
1 6
3

-1
-1
6

3
1 4
5
2 4

EMPTY

출처: Devin.KR 자체 제작