小西和复制粘贴

题号：NC215149
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小西想写一个复制粘贴的工具帮她完成人均要参加的A+级竞赛。

给出参数 $S,n,m,k,a_i,b_i,c_i$ 。

现在给定一个只由小写字母组成的字符串 $S$ 作为初始内容，小西需要完成接下来的 $n$ 次操作。

每个操作由三个参数组成： $a_i,b_i,c_i$ ，表示复制S的第 $[a_i, b_i)$ 这一段字符串后插入到原字符串的 $c_i$ 位置，这里的索引都是0开始计算的，插入的意思是让复制的字符串的首位成为S的第 $c_i$ 位。

比如当 $S$ 为abcdef，操作为 $1,3,5$ 时，表示复制bc插入到第5个位置，所以结果为abcdebcf

此外，还给出一个最大长度 $m$ ，如果每次操作后 $S$ 的长度超过了 $m$ ，那么就只保留 $S$ 的前 $m$ 个字符。

比如当 $S$ 为abcdef， $m$ 为7，操作为 $1,3,5$ 时，表示复制bc插入到第5个位置，所以结果为abcdebcf，但长度超过了 $m$ ，所以结果变为abcdebc

小西想知道进行完这 $n$ 次操作后 $S$ 的前 $k$ 位的内容

第一行输入两个整数和
第二行为字符串
第三行输入一个整数
接下来行每行三个整数依次表示






表示的长度。保证每次操作的参数对当前的合法。

输出一行长度为的字符串表示操作完之后的前位的内容

示例1

复制

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

复制

fa

示例2

复制

复制

adedbf