{"raw_statement":[{"iden":"problem statement","content":"You are given a string $S$ consisting of `A`, `B`, `C`.\nLet $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`.\nAnswer $Q$ queries. The $i$\\-th query is as follows.\n\n*   Print the $k_i$\\-th character from the beginning of $S^{(t_i)}$."},{"iden":"constraints","content":"*   $S$ is a string of length between $1$ and $10^5$ (inclusive) consisting of `A`, `B`, `C`.\n*   $1 \\leq Q \\leq 10^5$\n*   $0 \\leq t_i \\leq 10^{18}$\n*   $1 \\leq k_i \\leq \\min(10^{18},$ the length of $S^{(t_i)})$\n*   $Q, t_i, k_i$ are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$S$\n$Q$\n$t_1$ $k_1$\n$t_2$ $k_2$\n$\\hspace{0.4cm}\\vdots$\n$t_Q$ $k_Q$"},{"iden":"sample input 1","content":"ABC\n4\n0 1\n1 1\n1 3\n1 6"},{"iden":"sample output 1","content":"A\nB\nC\nB\n\nWe have $S^{(0)}=$`ABC`, $S^{(1)}=$`BCCAAB`.\nThus, the answers to the queries are `A`, `B`, `C`, `B` in the given order."},{"iden":"sample input 2","content":"CBBAACCCCC\n5\n57530144230160008 659279164847814847\n29622990657296329 861239705300265164\n509705228051901259 994708708957785197\n176678501072691541 655134104344481648\n827291290937314275 407121144297426665"},{"iden":"sample output 2","content":"A\nA\nC\nA\nA"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}