06707. USACO·查找与替换 未做

Bessie 正在使用最新最强大的文本编辑软件 miV！它强大的查找替换功能可以找出小写英文字母 $c$ 的所有出现位置，并把每一处替换成一个非空的小写字母串 $s$。例如，给定字符串 "$\text{ball}$"，如果 Bessie 选择 $c$ 为 'l'、$s$ 为 "$\text{na}$"，那么给定的字符串就会变成 "$\text{banana}$"。

Bessie 从字符串 "$\text{a}$" 开始，经过若干次这样的查找替换操作，得到最终字符串 $S$。由于 $S$ 可能非常长，她想知道：给定 $l$ 和 $r$（$1\le l\le r\le \min (|S|,10^{18})$），$S_{l\dots r}$（$S$ 中从第 $l$ 个字符到第 $r$ 个字符、含两端的子串）是什么。

保证所有操作的 $|s|$ 之和不超过 $2\cdot 10^5$，且 $r-l+1\le 2\cdot 10^5$。

第一行包含 $l$、$r$ 和操作的数量。

接下来每行描述一个操作，包含该操作的 $c$ 和 $s$。所有字符均在 'a' 到 'z' 的范围内。

在一行中输出 $S_{l\dots r}$。

【样例解释】

字符串按如下方式变换：

【数据规模与约定】

• 测试点 2-7：$\sum |s|,r-l+1\le 2000$。

• 测试点 8-15：无附加限制。