Description

You need to develop a word processing software. At the beginning, input a string as the initial document. You may assume that the start of the document is the $0$-th character. The following operations must be supported:

• 1 str: Append insertion. Insert the string $\texttt{str}$ at the end of the document, and output the document string.
• 2 a b: Extract part of the document. Keep only $b$ characters starting from the $a$-th character of the document, and output the document string.
• 3 a str: Insert a segment. Insert the string $\texttt{str}$ before the $a$-th character in the document, and output the document string.
• 4 str: Find a substring. Output the earliest position of the string $\texttt{str}$ in the document; if it cannot be found, output $-1$.

To simplify the problem, the initial document and $\texttt{str}$ in each operation contain no spaces or newlines. There will be at most $q$ operations.

Input Format

The first line contains a positive integer $q$, representing the number of operations.

The second line contains a string $\texttt{str}$, representing the initial string.

Starting from the third line, the next $q$ lines each describe an operation, as shown in the problem description.

Output Format

Output a total of $q$ lines.

For each operation $1,2,3$, output a string as required.

For operation $4$, output an integer as required.

4
ILove
1 Luogu
2 5 5
3 3 guGugu
4 gu

ILoveLuogu
Luogu
LuoguGugugu
3

Hint

Constraints: $1 \leq q \le 100$, and the length of the initial string is $\leq 100$.

Translated by ChatGPT 5