一天晚上,马克意识到明天有一篇论文要交。他还没有写任何东西,所以马克决定随机复制粘贴提示中的子字符串来撰写论文。
更正式地说,提示是一个初始长度为 $$$n$$$ 的字符串 $$$s$$$。马克将执行复制粘贴操作 $$$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$$$ 个字母。
示例
输入 #1
2 4 3 3 mark 1 4 5 7 3 8 1 10 12 7 3 3 creamii 2 3 3 4 2 9 9 11 12
输出 #1
m a r e a r
注意
在第一个测试用例中,复制粘贴过程如下。
- 第一步是在末尾粘贴字符串 $$$\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{creamiirea}\color{red}{\texttt{reamiire}}$$$。