Arcade Podium

Medium · heap

An arcade shows a podium for its k best players. Nobody has played yet. You are given a list of operations: operations[i] is either "add" or "podium", and args[i] holds its arguments: [player, points] for an "add" and [] (empty) for a "podium".

"add" gives points more points to player. A player who has not been seen before starts from 0.
"podium" asks for the sum of the totals of the k players with the highest totals. If fewer than k players have been seen, it is the sum of all their totals.

Return a list with the answer to every "podium", in the order they appear.

Examples

Example 1

Input: k = 2, operations = ["add", "add", "podium", "add", "podium", "add", "podium"], args = [[7, 5], [3, 4], [], [9, 6], [], [3, 4], []]

Output: [9, 11, 14]

Two players have been seen at first, so the podium is 5 + 4. Player 9 arrives with 6, so the best two are 6 and 5. Player 3 then reaches 8, so the best two are 8 and 6.

Example 2

Input: k = 1, operations = ["podium", "add", "podium", "add", "podium"], args = [[], [4, 2], [], [8, 3], []]

Output: [0, 2, 3]

Nobody has played at first, so the first podium is 0. Then player 8 with 3 points beats player 4 with 2.

Constraints

1 <= k <= 10^4
1 <= len(operations) <= 2 * 10^4
len(args) == len(operations)
operations[i] is add or podium
0 <= player <= 10^5
1 <= points <= 1000