ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

NEERC 2013, Четвертьфинал Восточного подрегиона

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

C. CVS

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Йода: Визит на Камину собираюсь я совершить... На армию клонов взглянуть, созданную для Республики.
Клонеры с планеты Камину выращивают клонов, причём отменных. Таких хороших результатов они достигают за счёт того, что тщательно следят за эволюцией своих творений. Сейчас каминуане заняты тем, что разрабатывают новую технологию обучения, позволяющую повысить эффективность клонов. Чтобы было удобней следить за ходом экспериментов, клонеры разработали специальную систему контроля «Clone Version System». Эта система довольно проста в эксплуатации.
В распоряжении каминуан есть некоторый набор программ обучения. Эффективность клона зависит от того, какие программы и в каком порядке он усвоил. Каминуане могут обучить любого клона по одной из программ, если он ещё не усвоил её ранее. После обучения клон приобретает нужные знания, и программа считается усвоенной.
Для удобства проведения экспериментов каминуане предоставили себе возможность откатывать действие последней усвоенной клоном программы. Знания клона в случае отката возвращаются к уровню, когда программа ещё не была усвоена. Тогда этого клона в дальнейшем можно опять обучать по такой программе. Откаты можно совершать до тех пор, пока клон не вернётся к базовым знаниям.
Кроме отката также предусмотрена возможность переусвоения. В случае, если каминуанин по ошибке применил откат, он может его отменить. Система контроля хранит историю откатов каждого клона. При применении очередного отката в историю делается соответствующая запись. При переусвоении — запись стирается. В случае обучения (не переусвоения) вся история откатов данного клона стирается. Переусвоение можно применять до тех пор, пока в истории по клону существуют записи.
И наконец в системе есть возможность клонирования. В случае, если каминуанам нравится текущий вариант клона, они могут его расклонировать. То есть создать нового клона с той же последовательностью усвоенных программ и историей откатов.
Изначально у каминуан есть один клон, имеющий базовые знания. Помогите им с анализом хода экспериментов.

Исходные данные

В первой строке даны числа n — количество запросов и m — количество обучающих программ (1 ≤ n, m ≤ 5·105). Каждая из следующих n строк имеет один из перечисленных форматов:
  • learn ci pi. Обучить клона с номером ci по программе pi (1 ≤ pim).
  • rollback ci. Откатить последнюю программу у клона с номером ci.
  • relearn ci. Переусвоить последний откат у клона с номером ci.
  • clone ci. Клонировать клона с номером ci.
  • check ci. Вывести программу, которой клон с номером ci владеет и при этом усвоил последней.
Все команды корректны, в частности, к клону, уже владеющему некоторой программой, learn по ней же применяться не будет. К клону, не владеющему ни одной программой, не применяется rollback. А также relearn возможен только при непустой истории откатов. В запросах может фигурировать только уже существующий клон. Номера клонам присваиваются в порядке их возникновения. Клон, с которого каминуане начали свои эксперименты, имел номер один.

Результат

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

Пример

исходные данныерезультат
9 10
learn 1 5
learn 1 7
rollback 1
check 1
clone 1
relearn 2
check 2
rollback 1
check 1
5
7
basic
Автор задачи: Егор Щелконогов
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1992. CVS