文本编辑器的最重要功能之一是复制与粘贴。JOI 公司正在开发一款能够极速处理复制与粘贴操作的文本编辑器。作为 JOI 公司的一名优秀程序员，你被指派负责核心复制与粘贴功能的测试。由于这关系到 JOI 公司的命运，你必须编写一个既准确又高效的程序。

具体规范如下：最初，文件内容为一个字符串 $S$。随后，将进行 $N$ 次复制与粘贴操作。第 $i$ 次操作是将从位置 $A_i$ 到位置 $B_i$ 的字符串复制，并将其插入粘贴到原字符串的位置 $C_i$ 处。在此，位置 $x$ 指的是从字符串开头数过 $x$ 个字符后的位置（位置 $0$ 为字符串的开头）。例如，对于字符串 copypaste，位置 $6$ 指的是字符 ‘a’ 和字符 ‘s’ 之间的位置。位置 $9$ 指的是字符 ‘e’ 的后面，即该字符串的末尾。但是，如果操作后字符串的长度超过了 $M$，则会从字符串的右端开始依次删除字符，直到长度变为 $M$ 为止。

你的任务是为编辑器测试，求出 $N$ 次操作后所得字符串的前 $K$ 个字符。

题目描述

给定整数 $K$、字符串长度上限 $M$、初始字符串 $S$、操作次数 $N$ 以及 $N$ 次复制与粘贴操作的指令，编写一个程序，求出操作后字符串的前 $K$ 个字符。

输入格式

从标准输入读取以下内容：

• 第 $1$ 行包含两个整数 $K, M$，以空格分隔。$K$ 表示要输出的字符数，$M$ 表示字符串长度的上限。
• 第 $2$ 行包含字符串 $S$，表示初始字符串。
• 第 $3$ 行包含整数 $N$，表示操作次数。
• 接下来的 $N$ 行中，第 $i$ 行 ($1 \le i \le N$) 包含三个整数 $A_i, B_i, C_i$，以空格分隔。这表示第 $i$ 次操作是将从位置 $A_i$ 到位置 $B_i$ 的字符串复制，并插入粘贴到位置 $C_i$ 处。

输出格式

将 $N$ 次操作后字符串的前 $K$ 个字符输出到标准输出，占一行。

数据范围

所有输入数据满足以下条件：

• $1 \le K \le 200$
• $1 \le M \le 1\,000\,000\,000$
• $S$ 中的每个字符均为英文字母小写（‘a’ – ‘z’）
• $K \le (S \text{ 的长度}) \le \min\{M, 200\,000\}$
• $1 \le N \le 200\,000$
• 设第 $i$ 次操作前字符串的长度为 $L_i$，则 $0 \le A_i < B_i \le L_i$ 且 $0 \le C_i \le L_i$ ($1 \le i \le N$)

子任务

子任务 1 [10 分]

满足以下条件：

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

子任务 2 [90 分]

没有额外限制。

样例

样例输入 1

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

样例输出 1

ac

说明

在此例中，$N = 4$ 次复制与粘贴操作执行如下：

• 初始字符串为 copypaste。
• 第 $1$ 次操作，复制从位置 $3$ 到位置 $6$ 的字符串 ypa，并插入到位置 $8$，得到字符串 copypastypae。
• 第 $2$ 次操作，复制从位置 $1$ 到位置 $5$ 的字符串 opyp，并插入到位置 $2$，得到字符串 coopyppypastypae。
• 第 $3$ 次操作，复制从位置 $4$ 到位置 $12$ 的字符串 yppypast，并插入到位置 $1$，得到字符串 cyppypastoopyppypastypae，但由于长度超过了 $M = 18$，从右端删除字符，得到字符串 cyppypastoopyppypa。
• 第 $4$ 次操作，复制从位置 $17$ 到位置 $18$ 的字符串 a，并插入到位置 $0$，得到字符串 acyppypastoopyppypa，但由于长度超过了 $M = 18$，从右端删除字符，得到字符串 acyppypastoopyppyp。

因此，输出操作后字符串 acyppypastoopyppyp 的前 $K = 2$ 个字符 ac。

样例输入 2

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

样例输出 2

joioji