농장 창고의 사료 더미

문제

한 농장은 사료 자루를 좁은 창고의 받침대 위에 한 줄로 쌓아 보관한다. 받침대에는 처음에 아무 자루도 없다. 새 사료 자루가 도착하면 현재 더미의 맨 위에 올려놓는다. 창고의 구조상 사료를 꺼낼 때도 맨 위의 자루부터 꺼내야 하며, 중간이나 맨 아래의 자루를 먼저 꺼낼 수는 없다. 받침대에 쌓을 수 있는 자루 수에는 별도의 제한이 없다. 농장 관리 기록에는 입고 작업과 출고 요청이 시간순으로 적혀 있다. 입고 작업에는 새 자루 하나의 무게 x가 적혀 있다. 이 작업을 처리하면 무게가 x인 자루 하나가 더미의 맨 위에 추가된다. 무게가 같은 자루가 여러 개 있을 수 있으며, 이들은 각각 별개의 자루이다. 입고된 자루는 이후의 출고 요청을 처리하는 데 사용할 수 있다. 출고 요청에는 필요한 자루 수 k가 적혀 있다. 요청을 처리할 때 더미에 자루가 k개 이상 있다면 맨 위에서부터 정확히 k개를 꺼내 출고한다. 이때 꺼낸 자루들의 무게 합을 출고 결과로 기록한다. 꺼낸 자루는 창고에서 사라지므로 이후 요청에서 다시 사용할 수 없다. 무게가 더 가벼운 자루를 골라내거나 요청한 자루 수를 바꾸는 일은 허용되지 않는다. 현재 자루 수가 k개보다 적다면 그 출고 요청은 실패한다. 실패한 요청에서는 자루를 하나도 꺼내지 않으며, 요청 직전의 더미가 그대로 유지된다. 실패한 요청을 나중으로 미루어 다시 처리하지도 않는다. 관리자는 해당 요청의 결과로 -1을 기록한 뒤 곧바로 다음 작업을 수행한다. 주어진 모든 작업을 순서대로 처리했을 때 각 출고 요청의 결과를 구한다. 성공한 출고 요청에서는 실제로 꺼낸 자루들의 무게 합을 출력하고, 실패한 요청에서는 -1을 출력한다. 입고 작업 자체의 결과는 출력하지 않는다. 모든 자루의 무게가 양의 정수이므로 성공한 출고 결과와 실패를 나타내는 -1은 구별된다.

입력

첫째 줄에 작업 수인 정수 Q가 주어진다. 1 ≤ Q ≤ 20,000이다.
다음 Q개 줄에 작업이 하나씩 주어진다.
1 x: 무게가 x인 자루 하나를 맨 위에 올린다. x는 정수이며 1 ≤ x ≤ 1,000,000,000이다.
2 k: 자루 k개의 출고를 요청한다. k는 정수이며 1 ≤ k ≤ Q이다.
모든 작업의 첫 번째 값은 1 또는 2이며, 출고 요청은 적어도 한 번 주어진다.

출력

각 출고 요청마다 결과를 한 줄에 하나씩 출력한다. 성공하면 꺼낸 자루들의 무게 합을 출력하고, 자루 수가 부족하면 -1을 출력한다. 출력 순서는 출고 요청이 주어진 순서와 같다.

9
1 8
1 13
2 1
1 5
2 3
1 11
2 2
2 1
2 1

13
-1
16
8
-1

7
2 1
1 1000000000
1 1000000000
1 1000000000
2 3
2 1
2 7

-1
3000000000
-1
-1

출처: Devin.KR 자체 제작