운동 매트 보관대

문제

한 헬스장에는 운동 매트를 가로로 늘어놓는 보관대가 있다. 보관대는 양쪽 끝이 열려 있어서 직원이 왼쪽이나 오른쪽에서 매트를 넣거나 꺼낼 수 있다. 매트에는 상태를 기록하기 위한 양의 정수 번호가 붙어 있다. 같은 번호가 붙은 매트가 여러 장 있을 수도 있으며, 번호가 같더라도 보관대에 놓인 매트는 각각 별개의 물건으로 취급한다. 처음에는 보관대가 비어 있다. 직원이 남긴 작업 기록은 네 종류다. 기록이 `1 x`이면 번호가 x인 매트 한 장을 보관대의 맨 왼쪽에 넣는다. 기록이 `2 x`이면 번호가 x인 매트 한 장을 맨 오른쪽에 넣는다. 기록이 `3`이면 맨 왼쪽 매트 한 장을 꺼내고 그 번호를 기록한다. 기록이 `4`이면 맨 오른쪽 매트 한 장을 꺼내고 그 번호를 기록한다. 매트를 넣을 때 기존 매트들의 상대적인 순서는 바뀌지 않는다. 꺼내기 작업을 수행할 때 보관대가 비어 있으면 아무 매트도 꺼내지 않고 -1을 기록한다. 이 작업 때문에 이후 작업을 건너뛰거나 작업 처리를 중단하지 않는다. 매트가 한 장만 있을 때에는 어느 쪽에서 꺼내더라도 그 매트를 꺼내며, 보관대는 다시 빈 상태가 된다. 보관대의 길이에는 제한이 없으므로 넣기 작업은 언제나 수행할 수 있다. 모든 작업은 입력에 주어진 순서대로 하나씩 완료한다. 번호의 크기는 보관 위치에 영향을 주지 않으며, 매트를 번호순으로 정렬하는 일도 없다. 넣기 작업에서는 출력할 내용을 만들지 않는다. 전체 작업이 끝난 뒤 남아 있는 매트의 번호 역시 출력하지 않는다. 주어진 작업 기록을 처리하여 각 꺼내기 작업에서 기록한 값을 순서대로 구해야 한다. 꺼내기 작업이 한 번도 없다면 출력할 기록이 없다는 뜻으로 EMPTY를 출력한다. 빈 보관대에서 꺼내기를 시도한 경우에는 EMPTY 대신 해당 작업의 기록인 -1을 출력해야 한다.

입력

첫째 줄에 작업 수 Q가 주어진다. Q는 1 이상 30,000 이하의 정수다.
다음 Q개 줄에 작업이 하나씩 주어진다. 각 작업은 `1 x`, `2 x`, `3`, `4` 중 하나다. x는 1 이상 1,000,000,000 이하의 정수다.

출력

종류가 3 또는 4인 작업마다 기록한 정수 하나를 한 줄에 출력한다. 보관대가 비어 있었다면 -1을 출력한다. 해당 작업이 한 번도 없다면 EMPTY를 한 줄에 출력한다.

8
2 30
1 12
2 45
3
4
4
3
1 9

12
45
30
-1

3
1 7
2 7
1 2

EMPTY

4
4
1 8
4
3

-1
8
-1

출처: Devin.KR 자체 제작