#2994. 「JOISC 2015 Day1」复制粘贴 2

题目描述

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

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

具体的操作如下。初始时文件内容为一个字符串 $S$，随后进行 $N$ 次复制粘贴操作。第 $i$ 次操作，先复制字符串中位置为 $A_i$ 与 $B_i$ 之间的子串，并将这部分插入到字符串的 $C_i$ 位置。这里，位置 $x$ 表示从字符串开头向后数 $x$ 个字符与后一个字符之间的位置（位置 $0$ 表示字符串的开头）。例如，字符串 $\text{copypaste}$ 的位置 $6$ 为字符 $\text{a}$ 与 $\text{s}$ 之间的位置，位置 $9$ 表示字符 $\text{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

解释
初始文本为 $\text{copypaste}$。

• 第一次操作，将位置 $3$ 到位置 $6$ 之间的文本 $\text{ypa}$ 复制到位置 $8$，文本变为 $\text{copypastypae}$。
• 第二次操作，将位置 $1$ 到位置 $5$ 之间的文本 $\text{opyp}$ 复制到位置 $8$，文本变为 $\text{coopyppypastypae}$。
• 第三次操作，将位置 $4$ 到位置 $12$ 之间的文本 $\text{yppypast}$ 复制到位置 $1$，文本变为 $\text{cyppypastoopyppypastypae}$。但是文本长度上限 $M=18$，从右向左删除文本中字符至文本长度为 $18$，文本变为 $\text{cyppypastoopyppypa}$。
• 第四次操作，将位置 $17$ 到位置 $18$ 之间的文本 $\text{a}$ 复制到位置 $0$，文本变为 $\text{acyppypastoopyppypa}$。但是文本长度上限 $M=18$，从右向左删除文本中字符至文本长度为 $18$，文本变为 $\text{acyppypastoopyppyp}$。

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

---

样例 2

输入

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$ 分）：无附加限制。