Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Игра (задача D II тура окружного этапа Всероссийской олимпиады школьников 2014 - 2015)

Задачу добавил: alef

Успешно сдано решений: 29


ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
input.txt
вывод
output.txt

В освободившихся помещениях газеты теперь открылся «Центр Развлечений ННнска». Поговаривали, что его владелец — то ли брат Хрушевелеву, то ли ещё какой родственник. Тех, кто заглядывал в центр развлечений, там всегда встречал немногословный молодой человек, представлявшийся Харитоном. Кто он в этом заведении — можно было только догадываться; впрочем, горожане предполагали, что Харитон как раз и является хозяином центра.

Особо любопытные посетители порой пытались расспросить Харитона — кто он, откуда приехал, и правда ли то, что про него говорят в городе. Харитон в таких случаях говорил, что готов ответить на любые вопросы, но только после того, как услышит правильные ответы на свои вопросы. А его вопросы были немного необычными.

Харитон предлагал посетителям сыграть с ним в следующую игру. У него есть n стаканов разного размера, при этом стакан с меньшим номером всегда помещается в стакан с большим номером.

Изначально все стаканы перевернуты вверх дном и стоят рядом. Харитон может взять какой-либо стакан и накрыть им любой другой стакан подходящего размера. Он проделывает это много раз, периодически спрашивая любопытного посетителя, под каким стаканом находится в настоящий момент стакан с некоторым номером #j. Посетитель должен указать самый верхний из накрывающих стакан #j стаканов (или собственно стакан #j, если он не накрыт никаким другим).

Ваша задача — по заданной последовательности действий Харитона получить ответы на его вопросы.

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

В первой строке содержатся целые числа n и q (1 ≤ n ≤ 2·105,  1 ≤ q ≤ 4·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
Примечание

Поясним приведённый пример.

  • Первое действие — перекладывание стакана #2 на стакан #1.
  • Второе действие — перекладывание стакана #3 на стакан #2.
  • Третье действие — вопрос, где находится стакан #1; правильный ответ — под стаканом #3.
  • Четвертое действие — перекладывание стакана #5 на стакан #4.
  • Пятое действие — вопрос, где находится стакан #5; правильный ответ — стакан #5 (он не накрыт никаким другим).
  • Шестое действие — перекладывание стакана #5 на стакан #3.
  • Седьмое действие — вопрос, где находится стакан #4; правильный ответ — стакан #4 (он не накрыт никаким другим).

Сдать задачу

Задать вопрос жюри по этой задаче