题目描述

译自 JOISC 2015 Day1 T1「コピー＆ペースト２ / Copy and Paste 2」

复制粘贴是文本编辑器最重要的功能之一，JOI 社正在开发一个可以快速处理复制粘贴操作的文本编辑器。作为 JOI 社的一名优秀的程序员，你的任务是测试复制粘贴功能的核心代码。由于 JOI 社危在旦夕，你需要确保这段核心代码准确高速。

具体的操作如下。初始时文件内容为一个字符串 $S$，随后进行 $N$ 次复制粘贴操作。第 $i$ 次操作，先复制字符串中位置为 $A_i$ 与 $B_i$ 之间的子串，并将这部分插入到字符串的 $C_i$ 位置。这里，位置 $x$ 表示从字符串开头向后数 $x$ 个字符与后一个字符之间的位置（位置 $0$ 表示字符串的开头）。例如，字符串 copypaste 的位置 $6$ 为字符 a 与 s 之间的位置，位置 $9$ 表示字符 e 的后面，也就是说，它代表了字符串的结尾。但是，如果操作后字符串长度超过 $M$，就会从字符串结尾删除字符，直到字符串长度为 $M$。

给定文本 $S$ 和 $N$ 次操作，你的任务是求出经过这 $N$ 次操作后文本 $S$ 的前 $K$ 个字符。

输入格式

第一行两个正整数 $K,M$，分别表示最后要输出文本 $S$ 的前 $K$ 个字符，文本 $S$ 长度的上限为 $M$。

第二行一个字符串 $S$，表示初始文本。

第三行一个正整数 $N$，表示操作次数。

接下来 $N$ 行，每行三个正整数 $A_i,B_i,C_i$，表示将文本 $S$ 中位置为 $A_i$ 到 $B_i$ 的部分复制插入到 $C_i$ 位置。

输出格式

一行一个长度为 $K$ 的字符串，表示最终答案。

样例 1

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

ac

初始文本为 copypaste。

第一次操作，将位置 $3$ 到位置 $6$ 之间的文本 ypa 复制到位置 $8$，文本变为 copypastypae。

第二次操作，将位置 $1$ 到位置 $5$ 之间的文本 opyp 复制到位置 $8$，文本变为 coopyppypastypae。

第三次操作，将位置 $4$ 到位置 $12$ 之间的文本 yppypast 复制到位置 $1$，文本变为 cyppypastoopyppypastypae。但是文本长度上限 $M=18$，从右向左删除文本中字符至文本长度为 $18$，文本变为 cyppypastoopyppypa。

第四次操作，将位置 $17$ 到位置 $18$ 之间的文本 a 复制到位置 $0$，文本变为 acyppypastoopyppypa。但是文本长度上限 $M=18$，从右向左删除文本中字符至文本长度为 $18$，文本变为 acyppypastoopyppyp。

最终，输出文本 acyppypastoopyppyp 的前 $K=2$ 个字符，即为 ac。

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

joioji

数据范围与提示

对于全部数据，$1\le K\le 200,1\le M\le 10^9,K\le |S|\le \min\{M,2\times 10^5\},1\le N\le 2\times 10^5$。保证 $S$ 由小写英文字母构成。设 $L_i$ 为第 $i$ 次操作之后文本 $S$ 的长度，保证 $0\le A_i<B_i\le L_i,0\le C_i\le L_i$。

详细子任务及附加限制如下：

• 子任务 $1$（$10$ 分）：$N\le 2\times 10^3,M\le 2\times 10^3$；
• 子任务 $2$（$90$ 分）：无附加限制。