AT_abc450_e [ABC450E] Fibonacci String

给定字符串 $X$ 和 $Y$，定义字符串序列 $S_1, S_2, \dots$ 如下： - $S_1 = X$ - $S_2 = Y$ - 对于 $i \geq 3$，$S_i$ 为 $S_{i-1}$ 与 $S_{i-2}$ 的连接（按此顺序）。 对于每个 $i = 1, 2, \ldots, Q$，请回答下述问题。 问题：给定整数 $L_i, R_i$ 以及字符 $C_i$，请统计字符 $C_i$ 在 $S_{10^{18}}$ 的第 $L_i$ 个到第 $R_i$ 个字符中出现了多少次。

输入通过标准输入给出，格式如下： > $X\\ Y\\ Q\\ L_1\ R_1\ C_1\\ L_2\ R_2\ C_2\\ \vdots\\ L_Q\ R_Q\ C_Q$

输出 $Q$ 行。 第 $i$ 行输出字符 $C_i$ 在 $S_{10^{18}}$ 的第 $L_i$ 到第 $R_i$ 个字符中出现的次数。

### 样例解释 1 $S_3, S_4, S_5$ 分别为 `ba`, `bab`, `babba`。 $S_{10^{18}}$ 是 `babbababbabba...`，第 2 到第 7 个字符包含了 3 个 `a`。 ### 数据范围 - $X$ 和 $Y$ 是由小写英文字母组成的字符串，长度在 $1$ 到 $10^4$ 之间（包括 $1$ 和 $10^4$）。 - $1 \leq Q \leq 10^5$ - $1 \leq L_i \leq R_i \leq 10^{18}$ - $C_i$ 为小写英文字母。 - 所有给出的数值均为整数。 由 ChatGPT 5 翻译