Сегодня Диппер нашел на чердаке странный аппарат. Он содержит n слотов, пронумерованных от 1 до n и расположенных подряд. В каждом слоте находится строка. Изначально во всех слотах находятся пустые строки. Аппарат может по заданным l, r и s добавить в конец всех строк, находящихся с l-го по r-й слот, строчку s.
Диппер поспорил с Мэйбл, что она не сможет смоделировать действия аппарата. Для этого он будет давать команды, а Мэйбл будет параллельно их повторять. Для проверки того, что Мэйбл безошибочно повторяет поведение аппарата, Диппер будет иногда спрашивать у Мэйбл следующий вопрос: чему равна подстрока с x по y в строке, находящейся в слоте i.
Мэйбл решила написать программу, которая будет моделировать этот процесс. Она просит вас помочь ей.
В первой строке находятся два натуральных числа n, m — количество слотов в аппарате и количество команд Диппера (1 ≤ n ≤ 2·105; 1 ≤ m ≤ 2·105).
В следующих m строках находятся m команд по одной в строке, каждая команда может быть одного из двух типов:
Гарантируется, что сумма длин строк, входящих в команды первого типа, не превосходит 106.
Гарантируется, что сумма длин подстрок по всем командам второго типа не превосходит 106.
На каждую команду второго типа нужно вывести ответ в отдельной строке.
4 4
1 2 2 two
1 2 3 aa
2 3 1 1
2 2 1 4
a
twoa
3 6
1 1 2 ab
1 2 3 cd
2 2 2 4
2 3 1 2
1 1 3 xyzu
2 1 2 5
bcd
cd
bxyz