CF1705C Mark and His Unfinished Essay

一天晚上，Mark 意识到明天要交一篇论文。他还什么都没写，于是决定随机从题目中复制粘贴一些子串来完成论文。 更正式地说，题目是一串初始长度为 $n$ 的字符串 $s$。Mark 将进行 $c$ 次复制粘贴操作。每次操作由两个整数 $l$ 和 $r$ 描述，表示 Mark 会将 $s_l s_{l+1} \ldots s_r$ 这一段字母追加到字符串 $s$ 的末尾。注意，每次操作后 $s$ 的长度会增加。 当然，Mark 需要能够看到已经写了什么。复制完成后，Mark 会提出 $q$ 个询问：给定一个整数 $k$，请你判断最终字符串 $s$ 的第 $k$ 个字母是什么。

第一行包含一个整数 $t$（$1\leq t\leq 1000$），表示测试用例的数量。 每个测试用例的第一行包含三个整数 $n$、$c$ 和 $q$（$1\leq n\leq 2\cdot 10^5$，$1\leq c\leq 40$，$1\leq q\leq 10^4$），分别表示初始字符串 $s$ 的长度、复制粘贴操作次数和询问次数。 每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$。保证 $s$ 只包含小写英文字母。 接下来的 $c$ 行，每行包含两个整数 $l$ 和 $r$（$1\leq l\leq r\leq 10^{18}$）。保证 $r$ 不会超过当前字符串 $s$ 的长度。 每个测试用例的最后 $q$ 行，每行包含一个整数 $k$（$1\leq k\leq 10^{18}$）。保证 $k$ 不会超过最终字符串 $s$ 的长度。 保证所有测试用例中 $n$ 和 $q$ 的总和分别不超过 $2\cdot 10^5$ 和 $10^4$。

对于每个询问，输出最终字符串 $s$ 的第 $k$ 个字母。

在第一个测试用例中，复制粘贴的过程如下： - 第一步，将字符串 $\texttt{mark}$ 粘贴到末尾，得到字符串 $\texttt{mark}\color{red}{\texttt{mark}}$。 - 第二步，将字符串 $\texttt{mar}$ 粘贴到末尾，得到字符串 $\texttt{markmark}\color{red}{\texttt{mar}}$。 - 第三步，将字符串 $\texttt{rkmark}$ 粘贴到末尾，得到字符串 $\texttt{markmarkmar}\color{red}{\texttt{rkmark}}$。 在第二个测试用例中，复制粘贴的过程如下： - 第一步，将字符串 $\texttt{re}$ 粘贴到末尾，得到字符串 $\texttt{creamii}\color{red}{\texttt{re}}$。 - 第二步，将字符串 $\texttt{ea}$ 粘贴到末尾，得到字符串 $\texttt{creamiire}\color{red}{\texttt{ea}}$。 - 第三步，将字符串 $\texttt{reamiire}$ 粘贴到末尾，得到字符串 $\texttt{creamiireea}\color{red}{\texttt{reamiire}}$。 由 ChatGPT 4.1 翻译