마라톤 급수대의 방향 전환

문제

한 마라톤 대회의 급수대에는 물을 기다리는 참가자들이 한 줄로 서 있다. 급수대는 통로의 양쪽 끝에 각각 물을 나누어 줄 수 있는 자리를 마련해 두었지만, 한 순간에는 한쪽 끝에서만 물을 나누어 준다. 현재 물을 나누어 주는 쪽을 줄의 앞, 반대쪽을 줄의 뒤라고 부른다. 처음에는 기다리는 참가자가 없다. 운영 기록에는 참가자의 합류, 급수 방향의 전환, 물 배부를 나타내는 세 종류의 명령이 주어진다. 모든 명령은 적힌 순서대로 실행하며, 한 명령을 처리하는 도중에 다른 명령이 끼어들지는 않는다. 참가자의 번호는 참가자를 구별하는 데 사용하며, 번호의 크기는 줄의 순서나 물을 받는 우선순위에 영향을 주지 않는다. 명령 JOIN x는 번호가 x인 참가자 한 명이 현재 줄의 뒤에 합류한다는 뜻이다. 새 참가자는 합류 직전에 기다리고 있던 모든 참가자보다 나중에 물을 받는 위치에 선다. 각 참가자 번호는 전체 운영 기록에서 한 번만 합류 명령에 등장한다. 명령 REVERSE는 물을 나누어 주는 쪽을 반대쪽 끝으로 바꾼다는 뜻이다. 이 명령을 실행하면 직전의 줄 뒤가 새로운 줄 앞이 되므로, 기다리던 참가자들의 앞에서 뒤로 본 순서가 완전히 뒤집힌다. 방향을 바꾼 뒤 합류하는 참가자도 새롭게 정해진 줄의 뒤에 선다. 기다리는 사람이 없거나 한 명뿐이어도 방향 전환 명령은 그대로 실행된다. 명령 SERVE k는 현재 줄의 앞부터 최대 k명에게 물을 나누어 준다는 뜻이다. 물을 받은 참가자는 즉시 줄에서 떠난다. 기다리는 참가자가 k명보다 적으면 모두에게 물을 주고, 아무도 없으면 누구에게도 물을 주지 않는다. 각 배부 명령에 대해 실제로 물을 받은 사람 수와 그 참가자들의 번호 합을 기록하려 한다. 모든 SERVE 명령의 기록을 구한다.

입력

첫째 줄에 명령의 개수 Q가 주어진다. Q는 정수이며 1 ≤ Q ≤ 20,000이다.
다음 Q개 줄에 JOIN x, REVERSE, SERVE k 중 하나의 명령이 주어진다. x와 k는 정수이며 1 ≤ x ≤ 100,000, 1 ≤ k ≤ 20,000이다. JOIN 명령에 등장하는 x는 모두 서로 다르다.
SERVE 명령이 적어도 한 번 주어진다.

출력

각 SERVE 명령에 대해 실제로 물을 받은 참가자 수와 그 참가자들의 번호 합을 공백으로 구분하여 한 줄에 출력한다. SERVE 명령이 주어진 순서대로 출력하며, 물을 받은 참가자가 없으면 0 0을 출력한다.

9
JOIN 12
JOIN 7
JOIN 20
REVERSE
SERVE 2
JOIN 5
REVERSE
SERVE 1
SERVE 3

2 27
1 5
1 12

6
SERVE 4
REVERSE
JOIN 9
REVERSE
JOIN 2
SERVE 5

0 0
2 11

출처: Devin.KR 자체 제작