Основною коштовністю на планеті Олімпія є камінці, які час від часу падають на поверхню планети з космосу. Що важчий камінець, то він цінніший. Щоб забезпечити функціонування планетарних установ, уряд час від часу збирає з містечок Олімпії податок. Із кожного з m містечок у столицю привозять по одному камінцю. Міністр вибирає з усіх камінців найважчий і бере його як податок. Решту m − 1 камінців відвозять назад у містечка, звідки їх привезли. Бажаючи заощадити, кожне містечко завжди везе у столицю найлегший з усіх коштовних камінців, які на даний момент має у своїй скарбниці.

Напишіть програму stones, яка, знаючи, в якому порядку в містечка падали камінці з космосу й маси цих камінців, для кожної події оподаткування визначить, камінець якої ваги уряд забрав як податок.

Вхідні дані

У першому рядку записано два числа: кількість подій 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-му вихідному рядку має бути записане одне число - маса камінця, взятого урядом як податок під час даної події.