창고 적재대의 출고 순서

문제

한 물류 창고에는 상자를 수직으로 쌓는 적재대가 하나 있다. 적재대의 옆면은 막혀 있어서 상자를 넣거나 꺼낼 때는 반드시 맨 위에서 작업한다. 처음 적재대는 비어 있다. 창고 관리 장치는 입고 작업과 출고 작업을 시간순으로 기록하며, 기록된 작업 하나를 끝낸 뒤 다음 작업을 시작한다. 입고 작업은 P W로 기록한다. 이는 무게가 W인 상자 하나를 현재 적재대의 맨 위에 올린다는 뜻이다. 상자의 무게는 양의 정수이며, 무게가 같은 상자도 서로 다른 상자다. 적재대에는 전체 작업에서 들어오는 모든 상자를 보관할 수 있는 공간이 있으므로 높이 제한을 고려하지 않는다. 출고 작업은 S C로 기록한다. 이 작업에서는 허용 적재 무게가 C인 빈 운반차 한 대를 사용한다. 담당자는 적재대 맨 위 상자의 무게가 운반차의 남은 허용 무게 이하이면 그 상자를 꺼내 운반차에 싣는다. 상자를 실을 때마다 남은 허용 무게에서 해당 상자의 무게를 뺀 뒤 같은 판단을 반복한다. 상자를 나누어 싣는 것은 허용하지 않는다. 적재대가 비거나, 맨 위 상자가 남은 허용 무게보다 무거워지는 순간 해당 출고 작업을 끝낸다. 무거운 상자를 잠시 옮겨 아래 상자를 꺼내거나, 더 많은 상자를 싣기 위해 이미 실은 상자를 되돌려 놓을 수 없다. 허용 무게를 정확히 채웠다면 남은 허용 무게는 0이며, 상자의 무게는 양수이므로 더 싣지 못한다. 출고된 상자는 적재대로 돌아오지 않는다. 다음 출고 작업에는 새로운 빈 운반차를 사용하므로 앞선 운반차의 남은 허용 무게가 이어지지 않는다. 작업 순서에 따라 적재대의 상태를 갱신하면서, 각 출고 작업에서 실제로 실은 상자의 개수와 그 상자들의 무게 합을 구한다. 상자를 하나도 싣지 못한 경우에는 두 값이 모두 0이다.

입력

첫째 줄에 작업 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 40,000이다.
다음 N개 줄에는 작업 하나가 주어진다. 입고 작업은 P W이며 W는 1 ≤ W ≤ 999인 정수다. 출고 작업은 S C이며 C는 0 ≤ C ≤ 999,999인 정수다.
출고 작업이 적어도 하나 주어진다. 작업은 입력 순서대로 수행한다.

출력

출고 작업마다 실은 상자의 개수와 무게 합을 공백으로 구분하여 한 줄에 출력한다. 출력 순서는 출고 작업이 입력된 순서와 같다. 입고 작업에는 출력하지 않는다.

9
P 4
P 7
P 2
S 8
S 11
S 5
P 3
P 3
S 6

1 2
2 11
0 0
2 6

6
S 10
P 5
S 0
P 2
S 4
S 5

0 0
0 0
1 2
1 5

출처: Devin.KR 자체 제작