{"problem":{"name":"ABC Transform","description":{"content":"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` → ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc242_d"},"statements":[{"statement_type":"Markdown","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)}$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc242_d","tags":[],"sample_group":[["ABC\n4\n0 1\n1 1\n1 3\n1 6","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."],["CBBAACCCCC\n5\n57530144230160008 659279164847814847\n29622990657296329 861239705300265164\n509705228051901259 994708708957785197\n176678501072691541 655134104344481648\n827291290937314275 407121144297426665","A\nA\nC\nA\nA"]],"created_at":"2026-03-03 11:01:14"}}