방향이 바뀌는 출고 줄

문제

물류 창고에서는 출고를 기다리는 상자를 한 줄로 관리한다. 줄에는 앞과 뒤가 있으며, 처음에는 상자가 하나도 없다. 각 상자에는 내용물의 수량을 나타내는 양의 정수가 적혀 있다. 서로 다른 상자에 같은 수량이 적혀 있을 수도 있다. 창고의 작업 기록에는 상자를 추가하거나 출고하거나 줄의 방향을 바꾸는 명령이 시간순으로 남아 있다. 명령 I x는 수량 x가 적힌 새 상자 하나를 현재 줄의 맨 뒤에 추가한다. 이미 기다리는 상자들의 상대적인 순서는 바뀌지 않는다. 줄이 비어 있었다면 새 상자가 유일한 상자가 된다. 상자에 적힌 수량은 추가된 뒤에도 변하지 않는다. 명령 O k는 현재 줄의 맨 앞에서부터 상자를 최대 k개 출고한다. 기다리는 상자가 k개 이상이면 정확히 k개를 출고하고, k개보다 적으면 기다리는 상자를 모두 출고한다. 출고된 상자는 줄에서 사라지며 이후 명령에 다시 등장하지 않는다. 이 명령을 처리할 때마다 실제로 출고한 상자의 개수와 그 상자들에 적힌 수량의 합을 기록한다. 줄이 비어 있다면 두 기록값은 모두 0이다. 명령 R은 현재 기다리는 상자들의 순서를 완전히 뒤집는다. 맨 앞 상자는 맨 뒤로, 맨 뒤 상자는 맨 앞으로 옮겨진다. 상자가 없거나 하나뿐이면 눈에 보이는 순서 변화는 없다. 방향을 바꾼 뒤의 추가와 출고도 새로 정해진 앞과 뒤를 기준으로 처리한다. 따라서 R 다음에 실행되는 I 명령은 뒤집힌 줄의 맨 뒤에 새 상자를 추가한다. 모든 명령은 주어진 순서대로 하나씩 끝까지 처리한다. 출고 요청을 나중으로 미루거나 부족한 상자를 추가로 만들지 않는다. 작업 기록이 주어질 때 각 O 명령의 출고 기록을 순서대로 구한다.

입력

첫째 줄에 명령 개수인 정수 N이 주어진다. 1 ≤ N ≤ 30,000이다.
다음 N개 줄에 명령이 하나씩 주어진다. 명령은 I x, O k, R 중 하나다. x와 k는 정수이며 1 ≤ x ≤ 1,000,000, 1 ≤ k ≤ 30,000이다.
O 명령은 적어도 한 번 주어진다.

출력

각 O 명령마다 실제로 출고한 상자 개수와 수량의 합을 공백으로 구분하여 한 줄에 출력한다. O 명령이 주어진 순서대로 출력하며, 출고한 상자가 없으면 0 0을 출력한다.

7
I 8
I 3
R
I 5
O 2
R
O 3

2 11
1 5

6
O 4
I 9
R
I 2
O 1
O 5

0 0
1 9
1 2

출처: Devin.KR 자체 제작