P9016 [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$ 和操作次数。

输出格式

一行，表示对应的子串。

输入输出样例 #1

输入 #1

3 8 4
a ab
a bc
c de
b bbb

输出 #1

bdebbb

说明/提示

$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$。