题目描述

给定一个由 A、B、C 组成的字符串 $S$。

令 $S^{(0)}:=S$。对于 $i=1,2,3,\\ldots$，令 $S^{(i)}$ 是将 $S^{(i-1)}$ 中的字符同时替换为以下内容得到的结果：A → BC，B → CA，C → AB。

回答 $Q$ 个查询问题。第 $i$ 个查询问题如下：

• 打印出 $S^{(t_i)}$ 开头的第 $k_i$ 个字符。

约束条件

• $S$ 是一个长度在 $1$ 到 $10^5$ 之间（包含边界）的字符串，由 A、B、C 组成。
• $1 \\leq Q \\leq 10^5$
• $0 \\leq t_i \\leq 10^{18}$
• $1 \\leq k_i \\leq \\min(10^{18},$ $S^{(t_i)}$ 的长度)
• $Q, t_i, k_i$ 是整数。

输入

从标准输入读入数据，输入格式如下：

$S$ $Q$ $t_1$ $k_1$ $t_2$ $k_2$ $\\hspace{0.4cm}\\vdots$ $t_Q$ $k_Q$

输出

按照索引的升序处理查询问题，即按照给定的顺序进行处理。每个答案后应跟随一个换行符。

示例输入1

ABC
4
0 1
1 1
1 3
1 6

示例输出1

A
B
C
B

我们有 $S^{(0)}=$ABC，$S^{(1)}=$BCCAAB。

因此，按照给定的顺序，查询问题的答案依次是 A、B、C、B。

示例输入2

CBBAACCCCC
5
57530144230160008 659279164847814847
29622990657296329 861239705300265164
509705228051901259 994708708957785197
176678501072691541 655134104344481648
827291290937314275 407121144297426665

示例输出2

A
A
C
A
A