Dipper and the Machine

Dipper found a strange machine in the attic today. The machine has $n$ slots numbered from 1 to $n$, placed in a row. Each slot holds a string. At the start, every slot holds an empty string. Given $l$, $r$, and $s$, the machine appends the string $s$ to the end of every string in slots $l$ through $r$.

Dipper bet Mabel that she cannot model the machine. Dipper issues commands, and Mabel repeats each one in parallel. To check that Mabel copies the machine's behavior exactly, Dipper sometimes asks: what is the substring from position $x$ to position $y$ of the string in slot $i$? Mabel wants a program that simulates this process. Help her.

The first line contains two positive integers $n$ and $m$, the number of slots and the number of Dipper's commands ($1 \le n \le 2 \cdot 10^5$; $1 \le m \le 2 \cdot 10^5$).

Each of the next $m$ lines contains one command, which has one of two types:

• 1 $l$ $r$ $s$: append the non-empty string $s$ to the end of every string in slots $l$ through $r$ inclusive ($1 \le l \le r \le n$). The string $s$ consists of lowercase Latin letters.
• 2 $i$ $x$ $y$: find the substring from $x$ to $y$ inclusive of the string in slot $i$ ($1 \le i \le n$; $1 \le x \le y$). The length of the string in slot $i$ is guaranteed to be at least $y$.

The total length of strings in type 1 commands does not exceed $10^6$. The total length of substrings requested by type 2 commands does not exceed $10^6$.

For each command of type 2, print the answer on a separate line.