分数: 450 点
问题陈述
给你字符串 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 出现在 L_i-th 通过 R_i- 第一个字符 S_{10^{18}}.
约束
- X 和 Y 是小写英文字母的字符串,长度介于 1 和 10^4,包括在内。
- 1 \leq Q \leq 10^5
- 1 \leq L_i \leq R_i \leq 10^{18}
- C_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 出现在 L_i-th 通过 R_i- 第一个字符 S_{10^{18}}.
示例输入 1
a b 6 2 7 a 1 3 b 3 7 b 1 9 c 1 1000000000000000000 b 1000000000000000000 1000000000000000000 a
示例输出 1
3 2 3 0 618033988749894848 1
S_3, S_4, S_5 是 ba, bab, babba。
S_{10^{18}} is babbababbabba...,第二个到第七个字符包含三次 a.