Copy and Paste

Time limit17sMemory limit512 MB

Summary

Apply N copy-and-paste operations to a string: each copies the substring from A to B and inserts it at C, then truncates the result to M characters.

Level: Medium7 of 10
Topics: String, Implementation
Solved: No attempts yet

Problem

One of the most important features of a text editor is copy and paste. JOI Inc. has started developing a text editor that handles copy and paste very quickly. You are a programmer at JOI Inc. and have been assigned to implement the core copy and paste logic. JOI Inc. depends on this work, so you want a program that is both accurate and fast.

Initially, the file contents are a string S. Then N copy and paste operations are performed. The i-th operation copies the substring from position A_i to position B_i and inserts the copied string at position C_i of the original string. Position x means the place right after the first x characters of the string, so position 0 is the start of the string. If the length of the string exceeds M after an operation, characters are deleted from the right end until the length is M.

Given the length limit M, the initial string S, the number of operations N, and the N copy and paste instructions, print the string after all N operations.

Input

The first line contains an integer M, the upper limit on the length of the string.

The second line contains the string S, 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, the number of operations. Line 3 + i (1 to N) contains three integers A_i, B_i, and C_i separated by spaces. Let L_i be the length of the string just before the i-th operation. Then $0 \le A_i < B_i \le L_i$ and $0 \le C_i \le L_i$ .

Output

Print the string after the N operations on one line.

Limits

$1 \le M \le 1000000$ (upper limit on the string length)

$1 \le N \le 1000000$ (number of operations)

Examples2

Example 1

Input

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

Expected output

acyppypastoopyppyp

Example 2
Input
```
100
joi
3
0 1 0
3 4 3
2 3 3
```
Expected output
```
jjooii
```