题目描述

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

我们定义 $S^{(0)} = S$。对于 $i = 1, 2, 3, \dots$，$S^{(i)}$ 是将 $S^{(i-1)}$ 中的所有字符按照以下规则同时进行替换后得到的字符串：

• A 替换为 BC
• B 替换为 CA
• C 替换为 AB

现在有 $Q$ 个查询，第 $i$ 个查询给出两个整数 $t_i$ 和 $k_i$，请你输出字符串 $S^{(t_i)}$ 从左往右数的第 $k_i$ 个字符。

输入格式

第一行包含一个字符串 $S$。

第二行包含一个正整数 $Q$ —— 查询的数量。

接下来 $Q$ 行，每行包含两个非负整数 $t_i$ 和 $k_i$ —— 分别表示第 $i$ 个查询的替换次数和字符位置。

输出格式

按照给定的顺序，逐行输出每个查询的结果（每次输出一个字符并换行）。

样例输入 1

ABC
4
0 1
1 1
1 3
1 6

样例输出 1

A
B
C
B

样例输入 2

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

样例输出 2

A
A
C
A
A

说明

样例解释

在第一个样例中，初始字符串为 $S^{(0)} = \text{ABC}$。 经过 $1$ 次替换后，字符串变为 $S^{(1)} = \text{BCCAAB}$。

• 第 $1$ 个查询要求输出 $S^{(0)}$ 的第 $1$ 个字符，即 A。
• 第 $2$ 个查询要求输出 $S^{(1)}$ 的第 $1$ 个字符，即 B。
• 第 $3$ 个查询要求输出 $S^{(1)}$ 的第 $3$ 个字符，即 C。
• 第 $4$ 个查询要求输出 $S^{(1)}$ 的第 $6$ 个字符，即 B。

因此，按照顺序分别输出 A, B, C, B。

数据范围

• 对于所有测试点，保证 $S$ 是一个长度在 $1$ 到 $10^5$ 之间（包含边界）的字符串，且仅由字符 A、B、C 组成。
• 对于所有测试点，保证 $1 \le Q \le 10^5$。
• 保证 $0 \le t_i \le 10^{18}$。
• 保证 $1 \le k_i \le \min(10^{18}, S^{(t_i)} \text{ 的长度})$。
• 保证所有的 $Q, t_i, k_i$ 均为整数。