题目描述

文本编辑器最重要的功能之一是复制与粘贴（复写・贴付）。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$ 个字符，占一行。

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

ac

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

joioji

提示

样例 1 解释

在这个例子中，$N = 4$ 次复制与粘贴操作按如下方式进行：

• 初始字符串为 copypaste。
• 第 1 次操作中，从位置 3 到位置 6 的子串 ypa 被复制，并在位置 8 插入粘贴，得到字符串 copypastypae。
• 第 2 次操作中，从位置 1 到位置 5 的子串 opyp 被复制，并在位置 2 插入粘贴，得到字符串 coopyppypastypae。
• 第 3 次操作中，从位置 4 到位置 12 的子串 yppypast 被复制，并在位置 1 插入粘贴，得到字符串 cyppypastooypyppypastypae，但由于长度超过 $M = 18$，因此从右端开始删除字符，最终得到字符串 cyppypastooypyppypa。
• 第 4 次操作中，从位置 17 到位置 18 的子串 a 被复制，并在位置 0 插入粘贴，得到字符串 acypypastooypyppypa，但由于长度超过 $M = 18$，因此从右端开始删除字符，最终得到字符串 acypypastooypyppyp。

因此，操作后字符串 acypypastooypyppyp 的前 $K = 2$ 个字符为 ac，输出该结果。

数据范围

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

• $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 分]

无额外限制。

翻译由 Qwen3-235B 完成