지원 창구의 양방향 대기열

문제

한 회사의 IT 지원 창구는 처리할 요청을 하나의 대기열로 관리한다. 대기열에는 앞과 뒤가 있으며, 담당자는 현재 앞에 있는 요청부터 처리한다. 일반 요청은 보통 뒤에 등록하지만 긴급 요청은 앞에 넣기도 한다. 교대 담당자가 업무를 인계받을 때에는 대기열 전체의 처리 방향을 뒤집을 수 있다. 처음에는 대기열이 비어 있다. 지원 기록에는 네 종류의 명령이 시간순으로 남아 있다. F x는 번호가 x인 요청을 현재 대기열의 맨 앞에 추가하는 명령이다. B x는 번호가 x인 요청을 현재 대기열의 맨 뒤에 추가하는 명령이다. C는 현재 맨 앞의 요청 하나를 꺼내 처리하는 명령이다. 이때 꺼낸 요청의 번호를 기록한다. 대기열이 비어 있다면 아무것도 꺼내지 않고 -1을 기록한다. R은 현재 대기열의 순서를 완전히 뒤집는 명령이다. 순서를 뒤집으면 이전의 맨 뒤 요청이 새로운 맨 앞 요청이 되고, 이전의 맨 앞 요청이 새로운 맨 뒤 요청이 된다. 이후 등장하는 F와 B도 뒤집힌 뒤의 현재 앞과 뒤를 기준으로 적용한다. 예를 들어 앞에서부터 4, 8, 2가 들어 있는 상태에서 R을 실행하면 순서는 2, 8, 4가 된다. 이 상태에서 F 6을 실행하면 순서는 6, 2, 8, 4가 된다. 빈 대기열이나 요청이 하나뿐인 대기열에 R을 실행해도 오류는 발생하지 않는다. 요청 번호는 업무의 종류를 나타내므로 같은 번호의 요청이 여러 번 등록될 수 있다. 같은 번호라도 각각 독립적인 요청으로 취급하며, C 명령 한 번은 요청을 최대 하나만 제거한다. 대기열의 길이에는 별도의 제한이 없고, 명령에 의해서만 내용이 바뀐다. 주어진 모든 명령을 차례대로 실행했을 때 C 명령이 남기는 기록을 구한다. C 명령이 한 번도 없다면 기록 대신 NONE을 출력한다.

입력

첫째 줄에 명령 수 Q가 주어진다. 다음 Q개의 줄에 F x, B x, C, R 중 하나의 명령이 주어진다. Q와 요청 번호 x는 정수이며 1 ≤ Q ≤ 40,000, 0 ≤ x ≤ 9,999다. C 또는 R 뒤에는 추가 값이 주어지지 않는다.

출력

각 C 명령의 처리 결과를 명령이 등장한 순서대로 한 줄에 하나씩 출력한다. 처리할 요청이 없었던 C 명령의 결과는 -1이다. C 명령이 한 번도 없다면 NONE을 한 줄에 출력한다.

8
F 10
B 20
R
C
F 30
C
C
C

20
30
10
-1

3
F 1
R
B 2

NONE

5
R
B 7
R
C
C

7
-1

출처: Devin.KR 자체 제작