← 返回题目列表

AtCoder · abc242_d

G. ABC 变换

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

给你一个字符串 S 组成 A, B, C.

让 S^{(0)}:=S。对于 i=1,2,3,\ldots,让 S^{(i)} 是同时替换字符的结果 S^{(i-1)} 如下: A → BC, B → CA, C → AB.

回答 Q 查询。的 i第查询如下。

  • 打印 k_i- 从开头算起的第一个字符 S^{(t_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

输出

处理 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