급식실의 배식대 접시

문제

학교 급식실에서는 배식을 시작하기 전에 접시를 한 줄로 쌓아 둔다. 접시마다 관리 번호가 적혀 있으며, 한 번에 들여오는 접시는 모두 같은 관리 번호를 가진다. 배식대에는 접시를 위로만 올릴 수 있고, 학생에게 내줄 때에도 맨 위의 접시부터 꺼내야 한다. 기록을 처리하기 전에는 배식대가 비어 있다. 급식 담당자가 남긴 기록은 두 종류다. `P x c`는 관리 번호가 x인 접시 c개를 현재 접시 더미의 맨 위에 올렸다는 뜻이다. 같은 관리 번호가 여러 기록에 등장할 수 있으며, 이 경우에도 각 기록이 등장한 순서대로 접시를 올린다. 관리 번호는 접시를 구별하는 표식일 뿐이며, 번호의 크기에 따라 쌓는 순서를 바꾸지는 않는다. `S c`는 학생들에게 접시 c개를 내주려고 했다는 뜻이다. 접시가 충분하면 맨 위에서부터 정확히 c개를 꺼낸다. 접시가 c개보다 적으면 남아 있는 접시를 모두 꺼내고, 내주지 못한 개수를 부족 수량에 더한다. 부족 수량은 처음에 0이며 모든 배식 기록에 걸쳐 누적한다. 부족했던 접시를 나중에 들어온 접시로 소급하여 내주지는 않는다. 한 배식 기록을 처리하면서 서로 다른 관리 번호의 접시를 연달아 꺼낼 수도 있다. 접시를 꺼낸 뒤 아래에 있던 접시가 드러나면 그 접시가 새로운 맨 위 접시가 된다. 모든 기록은 입력 순서대로 한 번씩 처리한다. 각 입고 기록의 수량은 클 수 있으므로 접시를 한 개씩 나열한 기록은 주어지지 않는다. 모든 기록을 처리한 뒤 누적 부족 수량, 배식대에 남은 접시의 총개수, 맨 위 접시의 관리 번호를 구해야 한다. 마지막에 접시가 하나도 없으면 맨 위 접시의 관리 번호 대신 0을 사용한다. 관리 번호는 양의 정수이므로 이 값은 실제 접시의 번호와 혼동되지 않는다.

입력

첫째 줄에 기록 수 N이 주어진다. 다음 N개 줄에 `P x c` 또는 `S c`가 하나씩 주어진다. 모든 수는 정수이며 1 ≤ N ≤ 12,000, 1 ≤ x ≤ 999, 1 ≤ c ≤ 1,000,000이다. 각 기록은 설명한 두 형식 중 하나를 정확히 따른다.

출력

누적 부족 수량, 남은 접시의 총개수, 맨 위 접시의 관리 번호를 이 순서대로 공백으로 구분하여 한 줄에 출력한다. 남은 접시가 없으면 마지막 값은 0이다.

7
P 12 4
P 8 3
S 5
P 21 2
S 1
S 5
P 6 2

2 2 6

4
S 3
P 7 2
S 2
S 1

4 0 0

3
P 5 1000000
P 5 1000000
S 1

0 1999999 5

출처: Devin.KR 자체 제작