当前没有测试数据。

D - ABC转换

得分：400分

问题描述

给定一个由字符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$之间（包括边界值）。字符串$S$由字符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$

输出

按索引的升序，即给定顺序，处理$Q$个查询。每个答案应在一行后跟一个换行符。

ABC
4
0 1
1 1
1 3
1 6

A
B
C
B

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

因此，query的答案按给定的顺序是A、B、C、B。

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

A
A
C
A
A