Problem Description

Farmer John has $n$ strings, with the $i$-th string being $s_i$.

You need to support the following $q$ operations:

• 1 x y i: Insert the entire string $s_x$ after the $i$-th character of string $s_y$, updating $s_y$.
• 2 y: Query the string $s_y$.

For example, if $s_1 = \texttt{abc}$ and $s_2 = \texttt{xyz}$, after executing 1 2 1 2 (inserting $s_2$ after the 2nd character of $s_1$ and updating $s_1$), $s_1$ becomes $\texttt{abxyzc}$ and $s_2$ remains $\texttt{xyz}$.

Input Format

The first line contains two integers, representing the number of strings $n$ and the number of operations $q$.
The next $n$ lines each contain a string, with the $i$-th line being $s_i$.
The next $q$ lines each contain either four or two integers, representing each operation as described in the problem description.

Output Format

For each operation of type 2, output a single line containing the queried string.

Sample Input and Output

Input Sample #1

2 2
a
b
1 1 2 1
2 2

Output Sample #1

ba

Input Sample #2

3 6
abc
ijk
xyz
1 2 3 2
1 1 3 5
1 3 1 1
2 1
2 2
2 3

Output Sample #2

axyijkabczbc
ijk
xyijkabcz

Notes

Data Size and Constraints

• For 60% of the test cases, it is guaranteed that $i = |s_y|$.
• For 100% of the test cases, $1 \leq n, q \leq 10$, $1 \leq |s_i| \leq 10$. $1 \leq x, y \leq n$, $1 \leq i \leq |s_y|$.

Where $|s_y|$ represents the length of $s_y$ at the time of the corresponding operation, and $|s_i|$ represents the length of the string at input.

Provider: 一扶苏一

见题面 Input 部分

见题面 Output 部分