공연장 입장 호출기

문제

한 공연장은 일반 관객과 우선 관객을 서로 다른 대기 줄에 등록한다. 입장 호출기는 두 줄의 도착 순서를 지키면서 한 번에 한 명을 호출한다. 운영 기록에는 대기 등록, 대기 취소, 입장 호출 명령이 시간순으로 남아 있다. 처음에는 두 대기 줄이 모두 비어 있다. 'J x V' 명령은 번호 x인 우선 관객을 우선 줄의 맨 뒤에 등록하고, 'J x N' 명령은 번호 x인 일반 관객을 일반 줄의 맨 뒤에 등록한다. 관객 번호는 등록할 때마다 새로 사용되므로 한 번호가 두 번 등록되는 일은 없다. 'C x' 명령은 번호 x인 관객이 현재 기다리고 있다면 대기를 취소한다. 아직 등록되지 않았거나 이미 호출되었거나 이미 취소된 번호에 대한 취소 명령은 아무 효과가 없다. 'S' 명령은 다음 규칙으로 한 명을 호출한다. 한 줄에만 관객이 있으면 그 줄의 맨 앞 관객을 호출한다. 두 줄 모두 관객이 있으면, 직전에 연속으로 호출한 우선 관객이 두 명 이상인 경우 일반 줄의 맨 앞 관객을 호출하고, 그렇지 않으면 우선 줄의 맨 앞 관객을 호출한다. 취소된 관객은 줄에서 빠진 것으로 취급한다. 호출된 관객도 즉시 대기 줄에서 빠진다. 연속 우선 호출 횟수는 처음에 0이다. 우선 관객을 호출하면 1 증가하고, 일반 관객을 호출하면 0이 된다. 두 줄이 모두 비어 있는 상태에서 'S'를 실행하면 0을 출력하고 연속 우선 호출 횟수를 0으로 바꾼다. 등록과 취소 명령은 이 횟수를 바꾸지 않는다. 일반 줄이 비어 있으면 우선 관객을 계속 호출할 수 있으며, 이때도 연속 횟수는 증가한다. 각 'S' 명령이 호출한 관객 번호를 구한다.

입력

첫째 줄에 명령 수를 나타내는 정수 Q가 주어진다. 1 ≤ Q ≤ 20,000이다.
다음 Q개 줄에 'J x V', 'J x N', 'C x', 'S' 중 하나가 주어진다. x는 1 이상 Q 이하인 정수다. 모든 J 명령의 관객 번호는 서로 다르다. C 명령의 번호에는 추가 제한이 없다. S 명령은 적어도 하나 주어진다.

출력

S 명령마다 호출한 관객 번호를 한 줄에 하나씩 순서대로 출력한다. 해당 명령을 실행할 때 대기 중인 관객이 없으면 0을 출력한다.

10
J 1 V
J 2 V
J 3 V
J 4 N
S
S
S
S
S
S

1
2
4
3
0
0

10
J 1 V
J 2 N
C 1
S
C 2
S
J 3 V
C 3
C 3
S

2
0
0

9
J 1 V
J 2 V
S
S
J 3 V
J 4 N
C 9
S
S

1
2
4
3

출처: Devin.KR 자체 제작