| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 10 | 6 | 6 | 100.000% |
Сегодня Диппер нашел на чердаке странный аппарат. Он содержит $n$ слотов, пронумерованных от 1ドル$ до $n$ и расположенных подряд. В каждом слоте находится строка. Изначально во всех слотах находятся пустые строки. Аппарат может по заданным $l,ドル $r$ и $s$ добавить в конец всех строк, находящихся с $l$-го по $r$-й слот, строчку $s$.
Диппер поспорил с Мэйбл, что она не сможет смоделировать действия аппарата. Для этого он будет давать команды, а Мэйбл будет параллельно их повторять. Для проверки того, что Мэйбл безошибочно повторяет поведение аппарата, Диппер будет иногда спрашивать у Мэйбл следующий вопрос: чему равна подстрока с $x$ по $y$ в строке, находящейся в слоте $i$.
Мэйбл решила написать программу, которая будет моделировать этот процесс. Она просит вас помочь ей.
В первой строке находятся два натуральных числа $n,ドル $m$ --- количество слотов в аппарате и количество команд Диппера (1ドル \le n \le 2 \cdot 10^5$; 1ドル \le m \le 2 \cdot 10^5$).
В следующих $m$ строках находятся $m$ команд по одной в строке, каждая команда может быть одного из двух типов:
Гарантируется, что сумма длин строк, входящих в команды первого типа, не превосходит 10ドル^6$.
Гарантируется, что сумма длин подстрок по всем командам второго типа не превосходит 10ドル^6$.
На каждую команду второго типа нужно вывести ответ в отдельной строке.
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