천문대 관측 꾸러미 정산

문제

한 천문대는 야간 관측 참가자에게 판매할 관측 꾸러미를 창고에 보관한다. 꾸러미는 모두 같은 종류지만 행사별 할인 조건에 따라 주문마다 판매 단가가 다를 수 있다. 백엔드 담당자는 주문, 입고, 취소 이벤트를 받은 순서대로 처리하여 재고와 정산 정보를 계산해야 한다. 처리할 이벤트는 모두 N개이며, 입력에서 등장하는 순서대로 1번부터 N번까지 번호를 붙인다. 주문 이벤트에는 주문 수량 q와 꾸러미 한 개의 판매 단가 p가 기록되어 있다. 처리 직전의 재고가 q 이상이면 주문 전체를 승인한다. 승인하면 재고에서 q를 빼고 정산 금액에 q×p를 더한다. 재고가 부족하면 주문 전체를 거절하며 아무 값도 바꾸지 않는다. 일부 수량만 판매하거나, 거절한 주문을 나중에 다시 처리하는 일은 없다. 입고 이벤트에는 수량 q가 기록되어 있다. 입고를 처리하면 재고에 q를 더한다. 입고 자체는 정산 금액에 영향을 주지 않으며 별도의 보관 용량 제한도 없다. 취소 이벤트에는 이전 이벤트 번호 r이 기록되어 있다. r번 이벤트가 승인된 주문이고 아직 취소되지 않았다면 취소가 성공한다. 성공하면 그 주문에서 판매했던 수량을 재고에 돌려놓고, 당시 주문의 수량과 단가를 곱한 금액을 정산 금액에서 뺀다. r번 이벤트가 입고나 취소이거나, 거절된 주문이거나, 이미 취소된 주문이면 아무 값도 바꾸지 않는다. 취소한 주문을 다시 승인하는 기능은 없다. 처음 재고는 S개이고 정산 금액은 0이다. 모든 이벤트를 처리한 뒤의 재고, 정산 금액, 그리고 승인된 후 취소되지 않은 주문의 개수를 구한다. 마지막 값은 판매한 꾸러미 수량이 아니라 주문 건수다. 서로 다른 주문은 수량과 단가가 같아도 별개의 주문으로 센다. 정산 금액은 큰 정수가 될 수 있으므로 중간 계산과 출력에서 정확한 정수 값을 유지해야 한다.

입력

첫째 줄에 정수 S와 N이 주어진다. 0 ≤ S ≤ 1,000,000, 1 ≤ N ≤ 20,000이다.
이후 N개의 줄에 이벤트가 주어진다. 이 중 i번째 줄의 이벤트 번호는 i이다.
주문은 `1 q p` 형식이며, 정수 q와 p는 1 ≤ q ≤ 1,000, 1 ≤ p ≤ 1,000,000,000을 만족한다.
입고는 `2 q` 형식이며, q는 1 이상 1,000 이하의 정수이다.
취소는 `3 r` 형식이며, r은 1 ≤ r < i를 만족하는 정수이다. 따라서 첫 번째 이벤트는 취소일 수 없다.
입력에 위 세 형식 이외의 이벤트는 주어지지 않는다.

출력

모든 이벤트를 처리한 뒤의 재고, 정산 금액, 승인된 후 취소되지 않은 주문 건수를 이 순서대로 공백으로 구분하여 정수 세 개로 출력한다. 해당 값이 없으면 0을 출력한다. 정산 금액은 지수 표기나 자릿수 구분 기호 없이 출력한다.

8 7
1 5 100
1 4 70
2 3
1 4 90
3 1
3 2
1 6 80

1 840 2

0 6
1 1 7
3 1
2 2
1 2 9
3 4
3 4

2 0 0

1000000 3
1 1000 1000000000
1 1000 1000000000
3 1

999000 1000000000000 1

출처: Devin.KR 자체 제작