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

The specific specifications are as follows. Initially, the file content is a string $S$. Subsequently, $N$ copy and paste operations are performed. The $i$-th operation copies the substring from position $A_i$ to position $B_i$ and inserts it into the original string at position $C_i$. Here, position $x$ represents the location immediately after the first $x$ characters of the string (position 0 is the beginning of the string). For example, in the string copypaste, position 6 represents the space between the character 'a' and the character 's'. Position 9 represents the space after the character 'e', which is the end 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 until the length becomes $M$.

Your task is to determine the first $K$ characters of the string obtained after $N$ operations for testing the editor.

Input

Read the following from standard input:

• The first line contains integers $K$ and $M$ separated by a space. $K$ represents the number of characters to output, and $M$ represents the upper limit of the string length.
• The second line contains the string $S$, representing the initial string.
• The third line contains an integer $N$, representing the number of operations.
• The $i$-th line ($1 \le i \le N$) of the following $N$ lines contains integers $A_i$, $B_i$, and $C_i$ separated by spaces. This indicates that the $i$-th operation copies the substring from position $A_i$ to position $B_i$ and inserts it at position $C_i$.

Output

Output the first $K$ characters of the string after $N$ operations on a single line to standard output.

Constraints

All input data satisfy the following conditions:

• $1 \le K \le 200$.
• $1 \le M \le 1\,000\,000\,000$.
• Each character of $S$ is a lowercase English letter ('a' – 'z').
• $K \le (\text{length of } S) \le \min\{M, 200\,000\}$.
• $1 \le N \le 200\,000$.
• Let $L_i$ be 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$ ($1 \le i \le N$).

Subtasks

Subtask 1 [10 points]

The following conditions are satisfied:

• $M \le 2\,000$.
• $N \le 2\,000$.

Subtask 2 [90 points]

There are no additional constraints.

Examples

Input 1

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

Output 1

ac

Note 1

In this example, the $N = 4$ copy and paste operations are performed as follows:

• The initial string is copypaste.
• In the 1st operation, the substring ypa from position 3 to position 6 is copied and inserted at position 8, resulting in the string copypastypae.
• In the 2nd operation, the substring opyp from position 1 to position 5 is copied and inserted at position 2, resulting in the string coopyppypastypae.
• In the 3rd operation, the substring yppypast from position 4 to position 12 is copied and inserted at position 1, resulting in the string cyppypastoopyppypastypae. Since the length exceeds $M = 18$, characters are deleted from the right end, resulting in the string cyppypastoopyppypa.
• In the 4th operation, the substring a from position 17 to position 18 is copied and inserted at position 0, resulting in the string acyppypastoopyppypa. Since the length exceeds $M = 18$, characters are deleted from the right end, resulting in the string acyppypastoopyppyp.

Therefore, output the first $K = 2$ characters of the string acyppypastoopyppyp, which is ac.

Input 2

6 100
jjooii
3
5 6 2
4 6 1
1 2 3

Output 2

joioji