[USACO23JAN] Find and Replace G

#### 【题目描述】 你有一个字符串 $S$，最开始里面只有一个字符 $\text{a}$，之后你要对这个字符串进行若干次操作，每次将其中每一个字符 $c$ 替换成某个字符串 $s$（例如对于字符串 $\text{ball}$，将其中的 $\text{l}$ 替换为 $\text{na}$ 后将会变为 $\text{banana}$）。现在给定 $l,r$，你需要输出 $S_{l\ldots r}$（也就是 $S$ 的第 $l$ 个字符到第 $r$ 个字符对应的子串）是什么。 #### 【输入格式】 第一行三个整数，分别表示 $l,r$ 和操作次数。 接下来每一行一个字符 $c$ 和一个字符串 $s$，意义见题目描述。 #### 【输出格式】 一行，表示对应的子串。 #### 【数据范围】 $l,r\le\min(\left | S \right |,10^{18})$； $r-l+1\le2\times10^5$； $\sum\left | s \right | \le 2\times 10^5$。 所有的字符串都只包含小写字母 $\text{a}-\text{z}$。 其中对于测试点 $2-7$，满足： $r-l+1\le2000$，$\sum\left | s \right | \le 2000$。

Bessie is using the latest and greatest innovation in text-editing software, miV! Its powerful find-and-replace feature allows her to find all occurrences of a lowercase English letter $c$ and replace each with a nonempty string of lowercase letters $s$. For example, given the string `ball`, if Bessie selects $c$ to be `l` and $s$ to be `na`, the given string transforms into `banana`. Bessie starts with the string `a` and transforms it using a number of these find-and-replace operations, resulting in a final string $S$. Since $S$ could be massive, she wants to know, given $l$ and $r$ with $1 \le l \le r \min(|S|,10^{18})$, what $S_{l\cdots r}$ (the substring of $S$ from the $l$-th to the $r$-th character inclusive) is. It is guaranteed that the sum of $|s|$ over all operations is at most $2 \cdot 10^5$, and that $r−l+1 \le 2 \cdot 10^5$.

The first line contains $l, r$, and the number of operations. Each subsequent line describes one operation and contains $c$ and $s$ for that operation. All characters are in the range `a` through `z`.

Output the string $S_{l \cdots r}$ on a single line.

3 8 4
a ab
a bc
c de
b bbb

bdebbb

### Explanation for Sample 1 The string is transformed as follows: $$ \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.