#4647. string

题目描述

给定三个字符串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

数据范围与提示