Problem H
Octopus Game!

It is this time of annual Octopus Game, a survival game where the winner stands to win millions of dollars, sponsored by His Excellency, Lord Pooty! Today is Day $1$ of the Octopus Games where the first round of culling begins! You are tasked with organising the games for this glorious day.

Each participant is given a skill rating $S$. A Game played between $2$ participants and and for the purpose of planning, the participant will the higher skill rating will always win.

You would like to conduct at most $K$ rounds of games today. In each round, you can choose some participants and pair them. Each pair will play a game together. Then, after all the games in that round which will for the purposes of planning will happen simultaneously, the losers of each pair will be shot and eliminated from the competition! Notice that at every round, not everyone need to play, but a participant cannot be in more than one pair in a single round. You can have $0$ games happening in the round if you wish.

Nonetheless, the games will be spectated and you need to entertain the crowd. Each game will provide an entertainment value equal to the lower skill rating of the $2$ participants playing the game. As such, you would like to plan the matches so as to maximise the total entertainment value over all games in all round. As mentioned before, for the purposes of planning, the participant with the lower skill rating will be assumed to lose and eliminated. If two participants are of the same rating, one will be shot at random (you can convince yourself it does not matter). An eliminated participant can’t play future rounds (because he will be dead!)

You want to find the maximum possible entertainment value for the day. Normally that would be easy but….

Alas, it is still the registration phase and there are still people registering and deregistering for the chance to win big. As such you want to know the maximum possible entertainment value currently possible at all times during this phase.

You start with an empty list of participants. You will receive queries of $2$ kinds, registration and deregistration. At every registration, you get the person’s ID and his skill rating. At every deregistration, you get the ID of the coward that is withdrawing. It is assumed that the ID of the withdrawing coward is valid (the ID has been registered and not deregistered). For simplicity, the registration ID will be in increasing order.

Lord Pooty is expecting a good show tonight so do help yourself if you want to see tomorrow!

The problem is also interactive so you must answer a query before reading the next one!

Input

The first line contains integers $Q$, $K$ ($1 \leq Q \leq 100\, 000$, $1 \leq K \leq 4$). $Q$ is the number of queries and $K$ is the number of rounds. This is followed by $Q$ lines of either $2$ forms:

• $1$ $i$ $S$ meaning the person of ID $i$ and skill rating $S$ is registering ($1 \leq i \leq 1\, 000\, 000$, $1 \leq S \leq 1\, 000\, 000\, 000$).

• $2$ $i$ meaning the person of ID $i$ is deregistering ($1 \leq i \leq 1\, 000\, 000$).

The $i$ for the $1$st query type will be distinct and in increasing order for simplicity. The $i$ for the $2$nd query type will be guaranteed to be valid (the ID is currently registered).

Output

After each query, print an integer denoting the maximum possible entertainment value!

9 2
1 1 1
1 2 3
1 3 10
1 4 20
1 5 13
1 6 2
2 6
2 4
2 1

0
1
4
14
26
27
26
14
13