Space pebbles#4974
The main jewel on the planet Olympia is pebbles, that sometimes fall to the surface of the planet from space. The heavier the pebble, the more valuable it is. To ensure the functioning of the planetary institutions, the government from time to time collects a tax from the cities of Olympia. From each of the cities, one pebble is brought to the capital. The minister chooses the heaviest among all the pebbles and takes it as a tax. The remaining m - 1 pebbles are brought back to the cities from which they were brought. To save money, each city always carries to the capital the lightest of all the gems that it currently has in its treasury.
Write a program that, knowing the order in which pebbles fall from space into the cities and the masses of these pebbles, for each tax gathering event will determine what weight pebble the government took as a tax.
The first line contains two numbers: the number of events and the number of cities (2 \le m < n \le 2 \cdot 10^5). Each event is one of two types: either a pebble falls in a certain city (type ), or the government collects a tax (type ). The following lines contain descriptions of the corresponding events in the order in which they occurred. The first number of the line that sets the event is the event type ( or ).
1. If the first number of the line is , then after it the line contains two more positive integers and , where (1 \le t \le m) - the number of the city where the pebble fell, and (1 \le w < 10^9) - the weight of the pebble.
2. If the first number of the line is , then it is the only number in the line.
Before the first event in any city there was not any pebble. Input data guarantees the following conditions:
1. The masses of all pebbles that fell on the planet are pairwise different. 2. At the moment when the government collects the tax, in each of the cities there is at least one pebble. 3. The government collected the tax at least once.
Print as many lines as there are events of type in the input: for -th event of type the -th line should contain a single number - the mass of a pebble taken by the government as a tax on this event.
Primer 1