Шерлок Холмс очень ценит своего напарника Ватсона, но считает его не готовым противостоять уловкам уличных мошенников. Сегодня он сделал модель популярной игры в наперстки и тренирует доктора. У него есть n коробок разного размера, при этом коробка с меньшим номером всегда помещается в коробку с большим номером. Изначально все коробки перевернуты вверх дном и стоят рядом. Холмс может взять какую-либо коробку и накрыть ею любую другую меньшего размера. Он проделывает это много раз, периодически спрашивая Ватсона, под какой коробкой находится в настоящий момент коробка с номером #j. Ватсон должен указать номер самой верхней из накрывающих коробку #j коробки (или саму коробку #j, если она не накрыта никакой другой). Ваша задача — по заданной последовательности действий Шерлока подсказать ответы доброму, но очень невнимательному Ватсону. Поясним приведённый ниже пример. Первое действие — перекладывание коробки #2 на коробку #1. Второе действие — перекладывание коробки #3 на коробку #2. Третье действие — вопрос, где находится коробка #1; правильный ответ — под коробкой #3. Четвертое действие — перекладывание коробки #5 на коробку #4. Пятое действие — вопрос, где находится коробка #5; правильный ответ — коробка#5 (она не накрыта другими). Шестое действие — перекладывание коробки #5 на коробку #3. Седьмое действие — вопрос, где находится коробка #4; правильный ответ — коробка #4 (она не накрыта другими). Входные данные В первой строке содержатся целые числа n и q (1?n?2?105,1?q?1?105) — количество коробок и общее количество действий: перекладываний коробок и вопросов Холмса. В каждой из следующих q строк описывается либо корректное перекладывание коробки, либо вопрос. Описание перекладывания коробки начинается с числа 1, после которого через пробел следует сначала номер большей коробки, а затем — номер меньшей, которая будет накрыта коробкой большего размера. Гарантируется, что большая и меньшая коробка не накрыты никакими другими. Описание вопроса начинается с числа 2, после которого через пробел следует номер коробки, местоположение которой интересует Шерлока. Выходные данные Выведите ответы на вопросы Холмса — по одному в каждой строке. Ввод 5 7 1 2 1 1 3 2 2 1 1 5 4 2 5 1 5 3 2 4 Вывод 3 5 4