题目描述

小 Z 手上有一个仅由 ABC 组成的字符串。他每轮可以将字符串中的所有 $\tt A \rightarrow \tt BC,\tt B \rightarrow \tt CA,\tt C \rightarrow \tt AB$。如原字符串为 ABC，经过第一轮操作之后变为 BCCAAB，第二轮操作之后变为 CAABABBCBCCA。

现在他想知道经过第 $t$ 轮变化之后的字符串的第 $k$ 个字符是什么。

输入格式

第一行，字符串 $s$，仅由 ABC 构成。

第二行，一个正整数 $q$，表示询问组数。

接下来 $q$ 行，每行 $2$ 个正整数 $t,k$。

输出格式

$q$ 行，每行一个字符，表示询问结果。

输入输出样例

ABC
4
0 1
1 1
1 3
1 6

A
B
C
B

样例 $\tt \#1$说明

• 原字符串为 ABC，第 $0$ 轮操作即原字符串的第 $1$ 个字符为 $A$；经过第一轮操作之后变为 BCCAAB，其中第 $1,3,6$ 个字符分别为 $B,C,B$。

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

A
A
C
A
A

数据范围

• 对于 $30\%$ 的数据，$1\le |s| \le 100, 1\le q \le 100, 0\le t \le 5$
• 对于 $100\%$ 的数据，$1\le |s| \le 10^5, 1\le q \le 10^5, 0\le t \le 10^{18}, 1\le k\le min(10^{18}, |s^t|)$