文本编辑器的最重要功能之一是复制与粘贴。JOI 公司开始开发一款能极快处理复制与粘贴的文本编辑器。作为 JOI 公司的一名优秀程序员，你被指派负责实现核心的复制与粘贴处理逻辑。由于这关系到 JOI 公司的命运，你必须不惜一切代价编写出一个既准确又高效的程序。

具体规格如下：最初，文件内容为一个字符串 $S$。随后，进行 $N$ 次复制与粘贴操作。第 $i$ 次操作是将从位置 $A_i$ 到位置 $B_i$ 的字符串复制，并将复制的字符串插入粘贴到原字符串的位置 $C_i$。在此，位置 $x$ 表示从字符串开头数过 $x$ 个字符后的位置（位置 $0$ 表示字符串的开头）。但是，如果操作后字符串的长度超过了 $M$，则会从字符串的右端开始依次删除字符，直到长度变为 $M$ 为止。我们希望求出 $N$ 次操作后得到的字符串。

题目描述

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

数据范围

$1 \le M \le 1\,000\,000$ 字符串长度上限 $1 \le N \le 1\,000\,000$ 操作次数

输入格式

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

• 第 1 行包含一个整数 $M$，表示字符串长度上限。
• 第 2 行包含一个字符串 $S$，表示初始字符串。$S$ 由小写英文字母组成，长度在 $1$ 到 $M$ 之间。
• 第 3 行包含一个整数 $N$，表示操作次数。
• 第 $3+i$ 行（$1 \le i \le N$）包含以空格分隔的整数 $A_i, B_i, C_i$，表示第 $i$ 次操作是将从位置 $A_i$ 到位置 $B_i$ 的字符串复制并插入粘贴到位置 $C_i$。设第 $i$ 次操作前字符串的长度为 $L_i$，则满足 $0 \le A_i < B_i \le L_i$ 且 $0 \le C_i \le L_i$。

输出格式

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

子任务

在评分用数据中，有 $10\%$ 的分值满足 $M \le 100\,000$ 且 $N \le 100\,000$。

样例

样例输入 1

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

样例输出 1

acyppypastoopyppyp

说明

在该示例中，$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。

样例输入 2

100
joi
3
0 1 0
3 4 3
2 3 3

样例输出 2

jjooii