항공권 묶음의 최근 금액

문제

한 여행 준비실은 단체 여행자의 항공권을 발급된 순서대로 하나의 묶음에 기록한다. 처음에는 묶음에 항공권이 없다. 담당자는 항공권을 추가하거나 최근 항공권을 취소하며, 중간중간 최근에 남아 있는 항공권들의 금액 합을 확인한다. 항공권의 목적지나 탑승자 정보는 이 작업에 영향을 주지 않고, 발급 순서와 금액만 사용한다. 기록에는 세 종류의 명령이 등장한다. 명령 B p는 금액이 p인 항공권 한 장을 묶음의 맨 뒤에 추가한다. 금액이 같은 항공권도 각각 별개의 항공권이다. 새로 추가된 항공권은 그 시점에 남아 있는 모든 항공권보다 최근에 발급된 것으로 취급한다. 명령 C k는 현재 묶음에 남아 있는 항공권 중 가장 최근에 발급된 것부터 최대 k장을 취소한다. 남아 있는 항공권이 k장보다 적으면 전부 취소한다. 묶음이 비어 있을 때 이 명령을 실행하면 아무 변화도 없다. 취소된 항공권은 묶음에서 완전히 사라지며, 이후 항공권을 추가하더라도 취소된 항공권이 복구되지는 않는다. 명령 Q k는 현재 남아 있는 항공권 중 가장 최근에 발급된 최대 k장의 금액 합을 묻는다. 남아 있는 항공권이 k장보다 적으면 남은 모든 항공권의 금액을 더한다. 묶음이 비어 있으면 합은 0이다. 조회는 항공권을 취소하거나 순서를 바꾸지 않으므로, 같은 상태에서 같은 조회를 반복하면 같은 결과를 얻는다. 예를 들어 금액이 서로 다른 항공권이 여러 장 남아 있어도 금액의 크기로 순서를 정하지 않는다. 오직 추가된 순서에 따라 최근 항공권을 고른다. 모든 명령을 입력에 주어진 순서대로 처리하고, 각 조회 명령이 실행되는 순간의 금액 합을 구한다. 금액 합은 한 장의 금액보다 훨씬 커질 수 있다.

입력

첫째 줄에 명령의 개수 Q가 주어진다. Q는 정수이며 1 ≤ Q ≤ 25,000이다.
다음 Q개 줄에 명령이 하나씩 주어진다. 각 명령은 B p, C k, Q k 중 하나다. p와 k는 정수이며 1 ≤ p ≤ 1,000,000,000, 1 ≤ k ≤ 25,000이다.
조회 명령 Q k가 적어도 한 번 주어진다. 명령의 첫 글자인 Q와 첫째 줄의 명령 개수 Q는 문맥으로 구분한다.

출력

각 Q k 명령에 대한 금액 합을 명령이 주어진 순서대로 한 줄에 하나씩 정수로 출력한다. 합을 구할 항공권이 없으면 0을 출력한다.

9
B 120
B 80
Q 1
B 50
Q 5
C 2
Q 3
C 4
Q 2

80
250
120
0

2
C 7
Q 1

0

출처: Devin.KR 자체 제작