Copy and Paste 2

One of the most important features of a text editor is copy and paste. JOI Company is developing a text editor that handles copy and paste very quickly. As an excellent programmer working for JOI Company, you have been put in charge of testing the core copy-and-paste processing. The fate of JOI Company is at stake, so you want to write a program that is accurate and fast no matter what.

The exact specification is as follows. Initially, the contents of the file are a string S. Then N copy-and-paste operations are performed. The i-th operation copies the string from position Ai to position Bi and inserts the copied string at position Ci of the original string. Here position x denotes the spot immediately after advancing x characters from the beginning of the string (position 0 is the beginning of the string). For example, position 6 of the string copypaste denotes the spot between the character 'a' and the character 's'. Position 9 denotes the spot after the character 'e', that is, the end of this string. If the length of the string after an operation exceeds M, characters are deleted one by one from the right end of the string until the length becomes M.

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

Given the integer K, the maximum string length M, the initial string S, the number of operations N, and the instructions for the N copy-and-paste operations, write a program that finds the first K characters of the string after the operations.

The following input is read from standard input.

• The first line contains the integers K and M separated by a space. K is the number of characters to output, and M is the maximum string length.
• The second line contains the string S, the initial string.
• The third line contains the integer N, the number of operations.
• Of the following N lines, the i-th line (1 ≤ i ≤ N) contains the integers Ai, Bi, and Ci separated by spaces. This means that the i-th operation copies the string from position Ai to position Bi and inserts it at position Ci.

Print the first K characters of the string after the N operations on one line to standard output.

• 1 ≤ K ≤ 200.
• 1 ≤ M ≤ 1 000 000 000.
• Each character of S is a lowercase English letter ('a' – 'z').
• K ≤ (length of S) ≤ min{M, 200 000}.
• 1 ≤ N ≤ 200 000.
• Let Li be the length of the string immediately before the i-th operation. Then 0 ≤ Ai < Bi ≤ Li and 0 ≤ Ci ≤ Li (1 ≤ i ≤ N).