102423: [AtCoder]ABC242 D - ABC Transform
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Score : $400$ points
Problem Statement
You are given a string $S$ consisting of A, B, C.
Let $S^{(0)}:=S$. For $i=1,2,3,\ldots$, let $S^{(i)}$ be the result of simultaneously replacing the characters of $S^{(i-1)}$ as follows: A → BC, B → CA, C → AB.
Answer $Q$ queries. The $i$-th query is as follows.
- Print the $k_i$-th character from the beginning of $S^{(t_i)}$.
Constraints
- $S$ is a string of length between $1$ and $10^5$ (inclusive) consisting of
A,B,C. - $1 \leq Q \leq 10^5$
- $0 \leq t_i \leq 10^{18}$
- $1 \leq k_i \leq \min(10^{18},$ the length of $S^{(t_i)})$
- $Q, t_i, k_i$ are integers.
Input
Input is given from Standard Input in the following format:
$S$
$Q$
$t_1$ $k_1$
$t_2$ $k_2$
$\hspace{0.4cm}\vdots$
$t_Q$ $k_Q$
Output
Process the $Q$ queries in ascending order of index, that is, in the given order. Each answer should be followed by a newline.
Sample Input 1
ABC 4 0 1 1 1 1 3 1 6
Sample Output 1
A B C B
We have $S^{(0)}=$ABC, $S^{(1)}=$BCCAAB.
Thus, the answers to the queries are A, B, C, B in the given order.
Sample Input 2
CBBAACCCCC 5 57530144230160008 659279164847814847 29622990657296329 861239705300265164 509705228051901259 994708708957785197 176678501072691541 655134104344481648 827291290937314275 407121144297426665
Sample Output 2
A A C A A
Input
题意翻译
给定一个长度在 $[1,10^5]$ 范围内的，仅由`A`、`B`、`C`组成的字符串 $s$。令 $s_0=s$。从 $1$ 开始，$s_i$ 以如下规则由 $s_{i-1}$ 变化而来：用`BC`代替`A`，用`CA`代替`B`，用`AB`代替`C`。现在给出 $q$ 次询问，第 $i$ 次询问会给出两个整数 $t_i$ 和 $k_i$，请输出 $s_{t_i}$ 的前数第 $k_i$ 个字符。 数据保证 $1 \le q \le 10^5$，$0 \le t_i \le 10^{18}$，$1 \le k_i \le \min (10^{18},|s_{t_i}|)$，且这些数都是整数。Output
分数：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$是一个由`A`、`B`、`C`组成的字符串，长度在$1$到$10^5$（含）之间。
- $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