题目

backgrounds

夕阳镇第五幼儿园的zhangzj是字符串之神，AC自动机、AK自动机、factor Oracle、后缀数组、后缀树、后缀自动机、后缀平衡树、后缀仙人掌、后缀平面图他都会，一天他在回家路上捡到了三个字符串，他发现这些字符串很好玩，于是他想通过其中两个字符串构成一个长字符串，用第三个字符串在其中匹配，但是他着急找他的好♂友玩(hei)游(hei)戏(hei)，只好请你来帮忙。

content

给定三个字符串$a,b,c$，它们的字符集均为小写字母，即{$a,b,c,\dots,z$}。

令$F_0=a,F_1=b,\dots,F_i=F_{i-1}+F_{i-2}(i \leq 2)$。

其中$+$表示字符串的连接。

现在有$q$个询问，每次询问给定$n,l,r,L,R$，求在$F_n$的第$l$个到第$r$个字符组成的字符串中，$s$的第$L$个字符到第$R$个字符组成的字符串的出现次数。

input format

第一行一个字符串$a$。

第二行一个字符串$b$。

第三行一个字符串$s$。

第四行一个正整数$q$。

下接$q$行，每行五个数：$n,l,r,L,R$，表示询问。

output format

共$q$行，每行对应一个询问的答案。

sample input

a
b
bb
4
4 1 5 1 2
4 1 1 1 2
4 2 4 1 1
6 1 13 1 2

sample output

1
0
2
3

sample explanation

$F_0 = “a”$；

$F_1 = “b”$；

$F_2 = “ba”$；

$F_3 = “bab”$；

$F_4 = “babba”$；

$F_5 = “babbabab”$；

$F_6 = “babbababbabba”$。

constraints

对于$100\%$的数据，$1 \leq |F_n| \leq 10^{9}$，$1 \leq l \leq r \leq |F_n|$，$1 \leq L \leq R \leq |s|$，$1 \leq |a|, |b|, |s| \leq 10^4$，$1 \leq q \leq 10^4$。