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 m cities, one pebble is brought to the capital. The minister chooses the heaviest among all the stones and takes it as a tax. The remaining m - 1 stones 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 how much weight the government took as a tax.

Input

The first line contains two numbers: the number of events n and the number of cities m (2 ≤ m < n ≤ 2 * 105). Each event is one of two types: either a stone falls in a certain city (type 1), or the government collects a tax (type 2). The following n 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 (1 or 2).

1. If the first number of the line is 1, then after it the line contains two more positive integers t and w, where t (1 ≤ t ≤ m) - the number of the city where the pebble fell, and w (1 ≤ w < 109) - the weight of the pebble.

2. If the first number of the line is 2, then it is the only number in the line.

Before the first event in any city there was no any pebble. Input data guarantees the following conditions:

1. The masses of all pebbles that fell on the planet are different in pairs.
2. At the moment when the government collects the tax, in each of the m cities there are at least one pebble.
3. The government collected the tax at least once.

Output

Print as many lines as there are events of type 2 in the input: for i-th event of type 2 the i - th line should contain a single number - the mass of a pebble taken by the government as a tax on this event.