コピー&ペースト 2

题意翻译

### 题意描述 最初 JOI 君给了你一个字符串 $s$,现在对这个字符串进行 $n$ 次操作,每次操作使得位置 $a_i$ 到 $b_i$ 的子串挪到位置 $c_i$。这里的位置可以这样理解:第 $i$ 个位置就是这个字符串的第 $i$ 个字符与第 $i+1$ 个字符之间的空隙。 但是,JOI 君怕复制的东西太多,所以他觉得如果字符数超过 $m$ 个就清除第 $m$ 个字符之后的所有字符。 现在,JOI 君想知道通过这样的复制粘贴得到的最终的字符串的前 $k$ 个字符。 对于 $100\%$ 的数据,$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$。 ### 输入格式 第一行两个空格分隔的正整数 $K$ 和 $M$,表示最终输出的文字数量和字符串长度的上限。 第二行一个字符串 $S$,表示初始的字符串。 第三行一个整数 $N$,表示操作的次数。 接下来 $N$ 行,第 $i$ 行包含三个空格分隔的整数 $A_i,B_i,C_i$,表示第 $i$ 次操作将位置 $A_i$ 到 $B_i$ 之间的字符串复制,然后粘贴到位置 $C_i$。 ### 输出格式 输出一行一个长度为K的字符串,表示最终的字符串的长度为 $K$ 的前缀。 ### 样例解释 初始的字符串为 `copypaste`。 - 第一次操作将从位置 $3$ 到位置 $6$ 的字符串 `ypa` 复制,插入位置 $8$,得到字符串 `copypastypae`; - 第二次操作将从位置 $1$ 到位置 $5$ 的字符串 `opyp` 复制,插入位置 $2$,得到字符串 `coopyppypastypae`; - 第三次操作将从位置 $4$ 到位置 $12$ 的字符串 `yppypast` 复制,插入位置 $1$,得到字符串 `cyppypastoopyppypastypae`,由于长度超过了 $M=18$,删除超过的部分,得到 `cyppypastoopyppypa`。 - 第四次操作将从位置 $17$ 到位置 $18$ 的字符串 `a` 复制,插入位置 $0$,得到字符串 `acyppypastoopyppypa`,删除超过 $18$ 的部分得到 `acyppypastoopyppyp`。 最后输出长度为 $2$ 的前缀 `ac` 即为答案。 ### 数据范围及约定 - 对于 $40\%$ 的数据,$1\le N,M\le 2000$; - 对于 $100\%$ 的数据,$1\le K\le 200$,$1\le M\le 10^9$,$S$ 的每个字符都是小写英文字母,$K\le |S|<=\min(M,2\times 10^5)$,$1\le N\le 2\times 10^5$,设第 $i$ 次操作前的字符串长度为 $L_i$,那么 $0\le A_i<B_i\le L_i$ 且 $0\le C_i\le L_i\ (1\le i\le N)$。

题目描述

[problemUrl]: https://atcoder.jp/contests/joisc2015/tasks/joisc2015_a

输入输出格式

输入格式


输出格式


输入输出样例

暂无测试点