AT_abc242_d [ABC242D] ABC Transform

[problemUrl]: https://atcoder.jp/contests/abc242/tasks/abc242_d `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 $ $ Q $ $ t_1 $ $ k_1 $ $ t_2 $ $ k_2 $ $ \hspace{0.4cm}\vdots $ $ t_Q $ $ k_Q $

$ Q $ 個のクエリを添字の昇順に、すなわち与えられる順に処理し、出力ごとに改行せよ。

### 制約 - $ 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 $ は整数 ### Sample Explanation 1 $ S^{(0)}= $`ABC`, $ S^{(1)}= $`BCCAAB` です。 よって各クエリへの答えは順に `A`, `B`, `C`, `B` となります。