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 翻译