题目描述

给定两个只包含小写英文字母的字符串 $A$ 和 $B$。

定义一个字符串序列：

• $T_1 = A$
• $T_2 = B$
• 当 $i \ge 3$ 时，$T_i = T_{i-1} + T_{i-2}$

其中，$+$ 表示字符串拼接。

接下来有 $Q$ 次询问。每次询问给出两个整数 $L, R$ 和一个字符 $c$，你需要回答：

在字符串 $T_{10^{18}}$ 中，下标从 $L$ 到 $R$ 的这一段里，字符 $c$ 一共出现了多少次。

字符串下标从 $1$ 开始编号。

输入格式

第一行输入两个字符串 $A, B$。

第二行输入一个整数 $Q$，表示询问次数。

接下来 $Q$ 行，每行输入两个整数 $L, R$ 和一个小写字母 $c$，表示一次询问。

数据范围：

• $1 \le |A|, |B| \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $1 \le L \le R \le |T_{10^{18}}|$
• 所有询问中的字符串总长度、预处理规模满足题目实现要求，总字符规模不超过 $5 \times 10^5$

输出格式

对于每次询问，输出一行一个整数，表示答案。

a
b
6
2 7 a
1 3 b
3 7 b
1 9 c
1 1000000000000000000 b
1000000000000000000 1000000000000000000 a

3
2
3
0
618033988749894848
1