分数: 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