One of the most important features of a text editor is copy and paste. JOI Inc. has started developing a text editor that processes copy and paste operations extremely quickly. You, an excellent programmer at JOI Inc., have been assigned to implement the core copy and paste processing. Since the fate of JOI Inc. depends on it, you want to create an accurate and fast program at all costs.

The specific specifications are as follows. Initially, the content of the file is a string $S$. Subsequently, $N$ copy and paste operations are performed. The $i$-th operation consists of copying the substring from position $A_i$ to position $B_i$ and inserting it into the original string at position $C_i$. Here, position $x$ represents the location immediately after tracing $x$ characters from the beginning of the string (position 0 is the beginning of the string). However, if the length of the string exceeds $M$ after an operation, characters are deleted from the right end of the string one by one until the length becomes $M$. You want to find the string obtained after $N$ operations.

Task

Given the upper limit of the string length $M$, the initial string $S$, the number of operations $N$, and the instructions for $N$ copy and paste operations, write a program that outputs the string after the operations.

Constraints

• $1 \le M \le 1\,000\,000$ (Upper limit of the string length)
• $1 \le N \le 1\,000\,000$ (Number of operations)

Input

Read the following input from standard input:

• The first line contains an integer $M$, representing the upper limit of the string length.
• The second line contains a string $S$, representing the initial string. $S$ consists of lowercase English letters, and its length is between 1 and $M$ inclusive.
• The third line contains an integer $N$, representing the number of operations.
• The $(3+i)$-th line ($1 \le i \le N$) contains integers $A_i, B_i, C_i$ separated by spaces, representing that the $i$-th operation copies the substring from position $A_i$ to position $B_i$ and inserts it at position $C_i$. If $L_i$ is the length of the string immediately before the $i$-th operation, then $0 \le A_i < B_i \le L_i$ and $0 \le C_i \le L_i$ are satisfied.

Output

Output the string after $N$ operations in a single line to standard output.

Subtasks

For 10% of the test cases, $M \le 100\,000$ and $N \le 100\,000$ are satisfied.

Examples

Input 1

18
copypaste
4
3 6 8
1 5 2
4 12 1
17 18 0

Output 1

acyppypastoopyppyp

Input 2

100
joi
3
0 1 0
3 4 3
2 3 3

Output 2

jjooii