Клонеры с планеты Камину выращивают клонов, причём отменных. Таких хороших результатов они достигают за счёт того, что тщательно следят за эволюцией своих творений. Сейчас каминуане заняты тем, что разрабатывают новую технологию обучения, позволяющую повысить эффективность клонов. Чтобы было удобней следить за ходом экспериментов, клонеры разработали специальную систему контроля «Clone Version System». Эта система довольно проста в эксплуатации.

В распоряжении каминуан есть некоторый набор программ обучения. Эффективность клона зависит от того, какие программы и в каком порядке он усвоил. Каминуане могут обучить любого клона по одной из программ, если он ещё не усвоил её ранее. После обучения клон приобретает нужные знания, и программа считается усвоенной.

Для удобства проведения экспериментов каминуане предоставили себе возможность откатывать действие последней усвоенной клоном программы. Знания клона в случае отката возвращаются к уровню, когда программа ещё не была усвоена. Тогда этого клона в дальнейшем можно опять обучать по такой программе. Откаты можно совершать до тех пор, пока клон не вернётся к базовым знаниям.

Кроме отката также предусмотрена возможность переусвоения. В случае, если каминуанин по ошибке применил откат, он может его отменить. Система контроля хранит историю откатов каждого клона. При применении очередного отката в историю делается соответствующая запись. При переусвоении — запись стирается. В случае обучения (не переусвоения) вся история откатов данного клона стирается. Переусвоение можно применять до тех пор, пока в истории по клону существуют записи.

И наконец в системе есть возможность клонирования. В случае, если каминуанам нравится текущий вариант клона, они могут его расклонировать. То есть создать нового клона с той же последовательностью усвоенных программ и историей откатов.

Изначально у каминуан есть один клон, имеющий базовые знания. Помогите им с анализом хода экспериментов.

В первой строке даны числа n — количество запросов и m — количество обучающих программ (1 ≤ n, m ≤ 5·10⁵). Каждая из следующих n строк имеет один из перечисленных форматов:

• learn c_i p_i. Обучить клона с номером c_i по программе p_i (1 ≤ p_i ≤ m).
• rollback c_i. Откатить последнюю программу у клона с номером c_i.
• relearn c_i. Переусвоить последний откат у клона с номером c_i.
• clone c_i. Клонировать клона с номером c_i.
• check c_i. Вывести программу, которой клон с номером c_i владеет и при этом усвоил последней.

Все команды корректны, в частности, к клону, уже владеющему некоторой программой, learn по ней же применяться не будет. К клону, не владеющему ни одной программой, не применяется rollback. А также relearn возможен только при непустой истории откатов. В запросах может фигурировать только уже существующий клон. Номера клонам присваиваются в порядке их возникновения. Клон, с которого каминуане начали свои эксперименты, имел номер один.

После каждого запроса check c_i в отдельной строке выведите результат. Если клон владеет только базовыми знаниями, выведите basic, иначе — номер последней изученной программы.