本题使用标准输入、标准输出，无需读写题面中提到的文件。

题目描述

Bessie 正在使用最新最强的文本编辑软件 miV！它强大的查找并替换功能允许她找到某个小写英文字母 $c$ 的所有出现位置，并将每一次出现都替换为一个非空的小写字母字符串 $s$。例如，给定字符串 "$\texttt{ball}$"，如果 Bessie 选择 $c$ 为 'l'，$s$ 为 "$\texttt{na}$"，则该字符串会变为 "$\texttt{banana}$"。 Bessie 从字符串 "$\texttt{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}$。

3 8 4
a ab
a bc
c de
b bbb

bdebbb

提示

字符串的变换过程如下：

$$\texttt{a} \rightarrow \texttt{ab} \rightarrow \texttt{bcb} \rightarrow \texttt{bdeb} \rightarrow \texttt{bbbdebbb}$$

SCORING: Inputs 2-7: $\sum |s|, r-l+1\le 2000$ Inputs 8-15: No additional constraints. Problem credits: Benjamin Qi

来源

USACO|2023|Gold