급수대의 배부 기록

문제

마라톤 대회의 한 급수대에서는 물이 담긴 컵을 참가자에게 하나씩 나누어 준다. 참가자가 한꺼번에 몰리면 도착한 순서대로 줄을 서고, 운영 요원은 기록 장치에 남은 작업을 순서대로 처리한다. 작업은 참가자 도착, 컵 보충, 컵 배부의 세 종류다. 처음에는 대기 중인 참가자가 없으며, 급수대에는 정해진 수의 컵이 준비되어 있다. A x는 번호가 x인 참가자 한 명이 도착했다는 뜻이다. 도착한 참가자는 대기 줄의 맨 뒤에 선다. 모든 참가자 번호는 양의 정수이며, 전체 기록에서 같은 번호의 참가자가 두 번 도착하는 일은 없다. W k는 물이 담긴 컵 k개를 새로 가져왔다는 뜻이다. 보충한 컵은 즉시 재고에 더해진다. 참가자가 도착하거나 컵이 보충되는 것만으로 배부가 자동으로 이루어지지는 않는다. S k는 줄의 맨 앞부터 최대 k명에게 컵을 배부하는 작업이다. 한 참가자는 컵 하나를 받고 즉시 줄에서 빠진다. k명에게 배부했거나, 컵이 모두 떨어졌거나, 대기 줄이 비면 그 작업을 끝낸다. 따라서 실제 배부 인원은 k, 작업 직전의 컵 수, 작업 직전의 대기 인원 중 가장 작은 값이다. 줄에서 기다리다가 컵을 받지 못한 참가자는 원래 순서를 유지하며 다음 배부를 기다린다. 각 배부 작업이 끝날 때마다 실제로 컵을 받은 참가자 수와 그 작업에서 마지막으로 컵을 받은 참가자 번호를 기록한다. 한 명에게도 배부하지 못했다면 두 값 모두 0으로 기록한다. 마지막으로 모든 작업이 끝났을 때의 대기 인원과 남은 컵 수도 기록한다. 배부 작업이 하나도 없어도 마지막 상태는 반드시 보고한다. 주어진 순서대로 모든 작업을 처리한 결과를 구하는 프로그램을 작성한다.

입력

첫째 줄에 작업 수 Q와 처음 준비된 컵 수 C가 주어진다. Q는 1 이상 20,000 이하의 정수이고, C는 0 이상 1,000,000 이하의 정수다.
다음 Q개 줄에 작업이 하나씩 주어진다. 작업은 A x, W k, S k 중 하나다. x는 1 이상 100,000 이하의 정수이며 모든 A 작업에서 서로 다르다. W와 S의 k는 1 이상 1,000,000 이하의 정수다.

출력

각 S 작업에 대해 실제 배부 인원과 마지막 수령자 번호를 공백으로 구분하여 한 줄에 출력한다. 실제 배부 인원이 0이면 0 0을 출력한다. 모든 작업을 처리한 뒤에는 대기 인원과 남은 컵 수를 공백으로 구분하여 마지막 줄에 출력한다.

8 2
A 31
A 8
S 1
A 42
S 5
W 3
S 2
S 1

1 31
1 8
1 42
0 0
0 2

5 0
A 7
S 3
W 1
A 9
S 5

0 0
1 7
1 0

3 4
W 2
A 18
A 3

2 6

출처: Devin.KR 자체 제작