Copy and Paste 2

JOI Spring Training Camp 2014/15
Original Statement / Submission Site

Problem Statement

One of the most important features of a text editor is copy and paste. JOI Corporation is developing a text editor that performs copy-and-paste operations extremely quickly. As an excellent programmer working for JOI Corporation, you have been assigned to test the core copy-and-paste functionality. The future of the company depends on this project, so you want to write an accurate and efficient program.

The detailed specification is as follows. Initially, the contents of the file are the string S. Then, N copy-and-paste operations are performed.

In the i-th operation, the substring between positions A_i and B_i is copied and inserted at position C_i of the original string.

A position x is the location immediately after the first x characters of the string. Thus, position 0 is the beginning of the string. For example, in the string copypaste, position 6 is between the characters a and s, while position 9 is after the final character e, that is, at the end of the string.

If the length of the string exceeds M after an operation, characters are deleted one by one from the right end until the length becomes exactly M.

Your task is to determine in advance the first K characters of the string obtained after all N operations, so that the editor can be tested.

Task

Given the integer K, the maximum string length M, the initial string S, the number N of operations, and the instructions for those operations, determine the first K characters of the resulting string.

Input

The input is given from standard input in the following format:

K M
S
N
A1 B1 C1
A2 B2 C2
...
AN BN CN

The first line contains two integers K and M. Here, K is the number of characters to output, and M is the maximum allowed length of the string.
The second line contains the string S, representing the initial contents of the file.
The third line contains the integer N, the number of copy-and-paste operations.
Each of the next N lines contains three integers A_i, B_i, and C_i. In the i-th operation, the substring from position A_i to position B_i is copied and inserted at position C_i.

Output

Print one line containing the first K characters of the string obtained after all N operations.

Constraints

1 ≤ K ≤ 200
1 ≤ M ≤ 1000000000
Every character of S is a lowercase English letter.
K ≤ |S| ≤ min(M, 200000)
1 ≤ N ≤ 200000
Let L_i be the length of the string immediately before the i-th operation. Then:
- 0 ≤ A_i < B_i ≤ L_i
- 0 ≤ C_i ≤ L_i

Subtasks

Subtask 1 [10 points]

M ≤ 2000
N ≤ 2000

Subtask 2 [90 points]

There are no additional constraints.

Sample Input 1

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

Sample Output 1

ac

Explanation of Sample 1

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

Initially, the string is copypaste.
In the first operation, the substring ypa from position 3 to position 6 is copied and inserted at position 8, producing copypastypae.
In the second operation, the substring opyp from position 1 to position 5 is copied and inserted at position 2, producing coopyppypastypae.
In the third operation, the substring yppypast from position 4 to position 12 is copied and inserted at position 1, producing cyppypastoopyppypastypae. Since its length exceeds M = 18, characters are deleted from the right end, leaving cyppypastoopyppypa.
In the fourth operation, the substring a from position 17 to position 18 is copied and inserted at position 0, producing acyppypastoopyppypa. Since its length exceeds M = 18, characters are deleted from the right end, leaving acyppypastoopyppyp.

Therefore, the first K = 2 characters of the final string acyppypastoopyppyp are ac, which should be output.

Sample Input 2

Sample Output 2

joioji