Игра (задача D II тура окружного этапа Всероссийской олимпиады школьников 2014 - 2015)
Задачу добавил: alef
Успешно сдано решений: 29
В освободившихся помещениях газеты теперь открылся «Центр Развлечений ННнска». Поговаривали, что его владелец — то ли брат Хрушевелеву, то ли ещё какой родственник. Тех, кто заглядывал в центр развлечений, там всегда встречал немногословный молодой человек, представлявшийся Харитоном. Кто он в этом заведении — можно было только догадываться; впрочем, горожане предполагали, что Харитон как раз и является хозяином центра.
Особо любопытные посетители порой пытались расспросить Харитона — кто он, откуда приехал, и правда ли то, что про него говорят в городе. Харитон в таких случаях говорил, что готов ответить на любые вопросы, но только после того, как услышит правильные ответы на свои вопросы. А его вопросы были немного необычными.
Харитон предлагал посетителям сыграть с ним в следующую игру. У него есть 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 (он не накрыт никаким другим).