양쪽 문이 열린 택배 보관대

문제

택배 분류실에는 왼쪽 문과 오른쪽 문이 있는 긴 보관대가 있다. 상자들은 보관대 안에서 한 줄로 놓이며, 두 문 중 어느 쪽에서도 상자를 넣거나 꺼낼 수 있다. 작업을 시작할 때 보관대는 비어 있다. 작업자는 주어진 작업 기록을 위에서부터 순서대로 처리한다. 각 상자에는 1부터 9까지의 정수인 분류 번호가 적혀 있다. 분류 번호가 같은 상자가 여러 개 있을 수 있으며, 그런 상자들도 각각 별개의 상자로 취급한다. 새 상자를 넣을 때 기존 상자들의 상대적인 순서는 바뀌지 않는다. 왼쪽 문으로 넣은 상자는 현재 모든 상자의 왼쪽에 놓이고, 오른쪽 문으로 넣은 상자는 현재 모든 상자의 오른쪽에 놓인다. 작업 기록은 네 종류다. `L x`는 분류 번호가 x인 상자 하나를 왼쪽 문으로 넣는 작업이고, `R x`는 같은 상자를 오른쪽 문으로 넣는 작업이다. `F`는 왼쪽 끝의 상자 하나를 꺼내는 작업이고, `B`는 오른쪽 끝의 상자 하나를 꺼내는 작업이다. 상자를 꺼냈다면 그 상자의 분류 번호를 기록한다. 보관대가 비어 있어 꺼낼 상자가 없다면 -1을 기록하며, 보관대는 그대로 빈 상태로 남는다. 꺼내기 작업은 성공 여부와 관계없이 정확히 하나의 기록을 만든다. 넣기 작업은 출력 기록을 만들지 않는다. 상자가 하나만 있을 때는 어느 문으로 꺼내더라도 그 상자가 제거된다. 작업의 순서를 바꾸거나 빈 보관대에서의 작업을 나중으로 미루지 않는다. 모든 작업을 처리하면서 만들어지는 기록을 발생한 순서대로 출력하는 프로그램을 작성한다.

입력

첫째 줄에 작업 수 N이 주어진다. N은 1 이상 90,000 이하의 정수다. 다음 N개 줄에는 작업이 하나씩 주어진다. 각 작업은 `L x`, `R x`, `F`, `B` 중 하나이며, x는 1 이상 9 이하의 정수다. F 또는 B 작업이 적어도 하나 주어진다.

출력

F 또는 B 작업마다 결과를 한 줄에 하나씩 출력한다. 상자를 꺼냈다면 그 분류 번호를, 꺼낼 상자가 없었다면 -1을 출력한다.

8
L 3
R 8
L 5
B
F
F
B
R 2

8
5
3
-1

6
F
R 4
L 4
B
B
F

-1
4
4
-1

출처: Devin.KR 자체 제작