IDE с системой управления версиями
Программисты часто используют системы контроля версий для управления файлами в своих проектах, однако в таких системах версии сохраняются только при ручной отправке изменений. Можете ли вы создать среду разработки (IDE), которая автоматически сохраняет новую версию каждый раз, когда вы вставляете или удаляете строку?
Позиции в буфере нумеруются с 1 слева направо. Изначально буфер пуст и находится в версии 0. Затем вы можете выполнять 3 типа команд (где vnow обозначает текущую версию до выполнения команды, а L[v] — длину буфера в версии v):
1 p s: вставить строку s после позиции p (0 ≤ p ≤ L[vnow], p=0 означает вставку перед началом буфера). Строка s содержит от 1 до 100 символов.
2 p c: удалить c символов, начиная с позиции p (p ≥ 1, p+c ≤ L[vnow]+1). Оставшиеся символы (если есть) сдвигаются влево, заполняя пустоту.
3 v p c: напечатать c символов, начиная с позиции p (p ≥ 1, p+c ≤ L[v]+1), в версии v (1 ≤ v ≤ vnow).
Первая команда всегда будет командой 1 (вставка). После выполнения каждой команды 1 или 2, версия увеличивается на 1.
Входные данные
Входные данные содержат один тестовый случай. Он начинается с одного целого числа n (1 ≤ n ≤ 50000), представляющего количество команд.
Каждая из следующих n строк содержит одну команду. Общая длина всех вставленных строк не превысит 1000000.
Выходные данные
Выведите результаты выполнения команд типа 3 в порядке их появления. Общая длина всех напечатанных строк не превысит 200000.
Обфускация
Чтобы предотвратить предварительную обработку команд, применяется следующая схема обфускации:
Каждая команда типа-1 преобразуется в 1 p+d s
Каждая команда типа-2 преобразуется в 2 p+d c+d
Каждая команда типа-3 преобразуется в 3 v+d p+d c+d
Где d — это количество напечатанных строчных букв 'c' до обработки этой команды.
После обфускации пример входных данных будет выглядеть так:
6
1 0 abcdefgh
2 4 3
3 1 2 5
3 3 3 4
1 4 xy
3 5 4 6
Это реальные входные данные, которые ваша программа будет обрабатывать.