Главной драгоценностью на планете Олимпия являются камешки, которые иногда падают на поверхность планеты из космоса. Чем тяжелее камешек, тем он ценнее. Чтобы обеспечить функционирование планетарных учреждений, правительство время от времени собирает с городов Олимпии налог. Из каждого из m городов в столицу привозят по одному камешку. Министр выбирает среди всех камешков самый тяжелый и берет его как налог. Оставшиеся m − 1 камешков отвозят назад в города, откуда их привезли. Чтобы сэкономить, каждый город всегда везет в столицу самый легкий из всех драгоценных камней, которые на данный момент имеет в своей сокровищнице.

Напишите программу, которая, зная, в каком порядке в города падали камешки из космоса и массы этих камешков, для каждого события сбора налога определит, камешек какого веса правительство взяло как налог.

Входные данные

В первой строке записаны два числа: количество событий n и количество городов m (2 ≤ m < n ≤ 2 * 105). Каждое событие бывает одного из двух типов: либо в некотором городе падает камешек (тип 1), либо правительство собирает налог (тип 2). Следующие n строк содержат описание соответствующих событий в том порядке, в котором они происходили. Первое число строки, которая задает событие, - это тип события (1 или 2).

1. Если первое число строки 1, то после него строка содержит еще два натуральных числа t и w, где t (1 ≤ t ≤ m) - номер города, куда упал камешек, а w (1 ≤ w < 109) - вес камешка.

2. Если первое число строки 2, то оно является единственным в строке.

Считаем, что перед первым событием ни в одном городе не было ни одного камешка. Входные данные гарантируют выполнение таких условий:

1. Массы всех камешков, которые падали на планету, попарно различны.
2. На момент, когда правительство собирает налог, в каждом из m городов есть хотя бы по одному камешку.
3. Правительство собрало налог хотя бы один раз.

Выходные данные

Вывести столько строк, сколько событий типа 2 задано на входе: для i-го по порядку события типа 2 в i-й строке должно быть записано единственное число - масса камешка, взятого правительством как налог при этом событии.