양쪽 문이 있는 출고 통로

문제

물류 창고에는 상자를 한 줄로 보관하는 임시 출고 통로가 있다. 통로의 왼쪽과 오른쪽에는 각각 문이 하나씩 있다. 작업자는 어느 문으로든 상자를 넣거나 꺼낼 수 있지만, 통로 가운데에 있는 상자를 직접 꺼내거나 상자의 순서를 바꿀 수는 없다. 처음에는 통로가 비어 있다. 각 상자에는 물품 종류를 나타내는 번호가 붙어 있다. 같은 종류의 상자가 여러 개 들어올 수 있으므로 번호가 같더라도 서로 다른 상자로 취급한다. 상자를 넣을 때는 선택한 문 바로 안쪽에 새 상자를 놓는다. 따라서 왼쪽으로 넣은 상자는 기존의 모든 상자보다 왼쪽에 놓이고, 오른쪽으로 넣은 상자는 기존의 모든 상자보다 오른쪽에 놓인다. 작업 기록은 네 가지 명령으로 이루어진다. L x는 번호가 x인 상자 하나를 왼쪽으로 넣는 명령이고, R x는 번호가 x인 상자 하나를 오른쪽으로 넣는 명령이다. F는 왼쪽 끝의 상자를 하나 꺼내는 명령이고, B는 오른쪽 끝의 상자를 하나 꺼내는 명령이다. 상자를 꺼낸 뒤에는 남은 상자들의 상대적인 순서가 유지된다. F 또는 B를 실행할 때 통로가 비어 있으면 아무 상자도 꺼내지 않는다. 이때도 해당 명령은 처리한 것으로 보며, 이후 명령은 정상적으로 이어서 실행한다. 상자가 한 개만 있을 때는 어느 쪽으로 꺼내더라도 그 상자가 통로에서 사라진다. 창고 관리자는 실제로 꺼낸 상자의 종류를 작업 순서대로 확인하려 한다. 모든 명령을 입력 순서대로 실행하고, F와 B가 등장할 때마다 꺼낸 상자의 번호를 기록한다. 꺼낼 상자가 없었던 경우에는 번호 대신 0을 기록한다. 상자를 넣는 명령에 대해서는 아무것도 기록하지 않는다.

입력

첫째 줄에 명령의 개수 Q가 주어진다. Q는 1 이상 50,000 이하의 정수다. 다음 Q개 줄에 명령이 하나씩 주어진다. 각 명령은 L x, R x, F, B 중 하나다. 상자 번호 x는 1 이상 9,999 이하의 정수다. F 또는 B 명령이 적어도 하나 주어진다.

출력

F 또는 B 명령마다 꺼낸 상자의 번호를 한 줄에 하나씩 출력한다. 해당 명령을 실행하기 직전에 통로가 비어 있었다면 0을 출력한다.

8
L 12
R 34
L 56
B
F
F
B
F

34
56
12
0
0

7
F
R 7
L 7
B
R 9
F
B

0
7
7
9

출처: Devin.KR 자체 제작