8647: BZOJ4647:string

Memory Limit:512 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

给定三个字符串a,b,c,它们的字符集均为小写字母,即a,b,c…z。 另F0=a,F1=b,,.,Fi=Fi-1+Fi-2(i <= 2) 其中十表示字符串的连接 现在有q个询问,每次询问给定n,l,r,L,R,求在Fn的第l个到第r个字符组 成的字符串中,s的第L个字符到第R个字符组成的字符串的出现次数。


输入格式

第一行一个字符串a 第二行一个字符串b 第三行一个字符串s 第四行一个正整数q 下接q行,每行五个数:n,l,r,L,R,表示询问 1<= |Fn|≤ 10^9,  I < l <=r<=|Fn|,  1≤ L≤ R<=|S| 1<=|a|,|b|,|S|<=10^4,1<=Q<=10000


输出格式

共q行,每行对应一个询问的答案


样例输入

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

样例输出

1
0
2
3

提示

没有写明提示


题目来源

没有写明来源

加入题单

算法标签: