28947번 - Диппер и аппарат 다국어

Сегодня Диппер нашел на чердаке странный аппарат. Он содержит $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$ команд по одной в строке, каждая команда может быть одного из двух типов:

• $1$ $l$ $r$ $s$ --- добавить в конец всех строк, находящихся с $l$-го по $r$-й слот включительно, непустую строку $s$ ($1 \le l \le r \le n$). Строка $s$ состоит из строчных латинских букв.
• $2$ $i$ $x$ $y$ --- узнать значение подстроки с $x$ по $y$ включительно у строки, находящейся в слоте $i$ ($1 \le i \le n$; $1 \le x \le y$). Гарантируется, что длина строки, находящейся в слоте под номером $i$, не меньше, чем $y$.

Гарантируется, что сумма длин строк, входящих в команды первого типа, не превосходит $10^6$.

Гарантируется, что сумма длин подстрок по всем командам второго типа не превосходит $10^6$.

На каждую команду второго типа нужно вывести ответ в отдельной строке.