CF1705C.Mark and His Unfinished Essay

One night, Mark realized that there is an essay due tomorrow. He hasn't written anything yet, so Mark decided to randomly copy-paste substrings from the prompt to make the essay.

More formally, the prompt is a string $s$ of initial length $n$. Mark will perform the copy-pasting operation $c$ times. Each operation is described by two integers $l$ and $r$, which means that Mark will append letters $s_l s_{l+1} \ldots s_r$ to the end of string $s$. Note that the length of $s$ increases after this operation.

Of course, Mark needs to be able to see what has been written. After copying, Mark will ask $q$ queries: given an integer $k$, determine the $k$-th letter of the final string $s$.

一天夜里，马克意识到明天有一篇论文要交。他至今一个字都没写，于是决定从题目提示中随机复制粘贴子串来完成这篇论文。

更准确地说，题目提示是一个初始长度为 $n$ 的字符串 $s$。马克将执行 $c$ 次复制粘贴操作。每次操作由两个整数 $l$ 和 $r$ 描述，表示马克将把子串 $s_l s_{l+1} \ldots s_r$ 追加到字符串 $s$ 的末尾。注意：该操作会使 $s$ 的长度增加。

当然，马克需要能查看已写入的内容。在所有复制操作完成后，马克会提出 $q$ 个查询：对每个给定的整数 $k$，确定最终字符串 $s$ 中第 $k$ 个字符。

The first line contains a single integer $t$ ($1\leq t\leq 1000$) — the number of test cases.

The first line of each test case contains three integers $n$, $c$, and $q$ ($1\leq n\leq 2\cdot 10^5$, $1\leq c\leq 40$, and $1\leq q\leq 10^4$) — the length of the initial string $s$, the number of copy-pasting operations, and the number of queries, respectively.

The second line of each test case contains a single string $s$ of length $n$. It is guaranteed that $s$ only contains lowercase English letters.

The following $c$ lines describe the copy-pasting operation. Each line contains two integers $l$ and $r$ ($1\leq l\leq r\leq 10^{18}$). It is also guaranteed that $r$ does not exceed the current length of $s$.

The last $q$ lines of each test case describe the queries. Each line contains a single integer $k$ ($1\leq k\leq 10^{18}$). It is also guaranteed that $k$ does not exceed the final length of $s$.

It is guaranteed that the sum of $n$ and $q$ across all test cases does not exceed $2\cdot 10^5$ and $10^4$, respectively.

第一行包含一个整数 $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$ 的总和不超过 $2\cdot 10^5$，且 $q$ 的总和不超过 $10^4$。

For each query, print the $k$-th letter of the final string $s$.

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

In the first test case, the copy-paste process is as follows.

• The first step is pasting string $\texttt{mark}$ at the end, yielding the string $\texttt{mark}\color{red}{\texttt{mark}}$.
• The second step is pasting string $\texttt{mar}$ at the end, yielding the string $\texttt{markmark}\color{red}{\texttt{mar}}$.
• The third step is pasting string $\texttt{rkmark}$ at the end, yielding the string $\texttt{markmarkmar}\color{red}{\texttt{rkmark}}$.

In the second test case, the copy-paste process is as follows.

• The first step is pasting string $\texttt{re}$ at the end, yielding the string $\texttt{creamii}\color{red}{\texttt{re}}$.
• The second step is pasting string $\texttt{ea}$ at the end, yielding the string $\texttt{creamiire}\color{red}{\texttt{ea}}$.
• The third step is pasting string $\texttt{reamiire}$ at the end, yielding the string $\texttt{creamiireea}\color{red}{\texttt{reamiire}}$.

在第一个测试用例中，复制-粘贴过程如下：

• 第一步：在末尾粘贴字符串 $\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}}$。