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: ABC, BCA, CAB.

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

加入题单

上一题 下一题 算法标签: