题目背景

海曙区“呦呦海贝”月赛即将开始，贝贝准备了一条由小写英文字母组成的海贝密语模板。

制作活动长卷时，贝贝每次都从模板的第一个字母开始，截取一段前缀，再把这些前缀依次拼接起来。小伙伴们想在长卷的指定区间中寻找某个目标密语，请你帮助贝贝完成统计。

题目描述

给定两个非空字符串 $S$ 和 $T$，以及 $n$ 个正整数 $a_1,a_2,\ldots,a_n$。

设 $S[1\ldots a_i]$ 表示 $S$ 的前 $a_i$ 个字符。按顺序拼接这些前缀，得到字符串

$$P=S[1\ldots a_1]+S[1\ldots a_2]+\cdots+S[1\ldots a_n],$$

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

接下来有 $q$ 次询问。每次给定两个整数 $l,r$，请计算 $T$ 在子串 $P[l\ldots r]$ 中出现的次数。

所有字符串的位置均从 $1$ 开始编号。一次出现必须完整包含在询问区间内。更形式化地，你需要统计满足以下条件的起始位置 $k$ 的数量：

• $l\leq k$ 且 $k+|T|-1\leq r$；
• $P[k\ldots k+|T|-1]=T$。

其中 $|T|$ 表示字符串 $T$ 的长度。

特别说明：

• 不同出现可以相互重叠。例如，aaa 在 aaaaa 中出现 $3$ 次。
• 一次出现可以跨越一个或多个前缀之间的拼接位置。
• 如果询问区间的长度小于 $|T|$，答案为 $0$。
• 所有询问相互独立，不会修改字符串。

输入格式

第一行包含字符串 $S$。

第二行包含字符串 $T$。

第三行包含一个正整数 $n$。

第四行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$。

第五行包含一个正整数 $q$。

接下来 $q$ 行，每行包含两个正整数 $l,r$，描述一次询问。

输出格式

输出 $q$ 行，每行一个整数，表示对应询问的答案。

样例 1

aabab
aba
4
4 5 1 4
8
1 14
5 10
1 7
4 10
2 8
5 9
8 8
8 14

4
2
1
2
2
1
0
2

样例 1 解释

拼接后得到 P=aaba+aabab+a+aaba= aabaaababaaaba。目标串 aba 的四次出现分别从位置 $2,6,8,12$ 开始。第一次询问包含全部四次出现。

样例 2

aaaa
aaa
3
2 1 4
8
1 7
2 6
3 4
1 3
2 4
5 7
7 7
1 6

5
3
0
1
1
1
0
4

样例 2 解释

拼接后得到 P= aaaaaaa。目标串 aaa 分别从位置 $1,2,3,4,5$ 开始出现，共 $5$ 次。这些出现可以重叠。区间 $[3,4]$ 长度不足 $3$，答案为 $0$。

样例 3

abcde
aaa
5
1 1 1 1 5
6
1 9
2 5
3 5
4 9
1 2
5 9

3
2
1
0
0
0

样例 3 解释

拼接后得到 P=a+ a+a+a+abcde=aaaaabcde。目标串 aaa 分别从位置 $1,2,3$ 开始出现。其中从位置 $1$ 开始的出现横跨前三个前缀段，说明一次匹配可以跨越多个拼接位置。

样例 4

ab
ababab
5
2 2 2 1 2
5
1 9
1 6
2 9
3 8
7 9

1
1
0
0
0

样例 4 解释

拼接后得到 P= ab+ ab+ab+a+ab=abababaab。目标串 ababab 比模板 ab 更长，但仍可以跨越前三个前缀段出现。唯一一次出现从位置 $1$ 开始，因此区间 $[2,9]$ 中没有完整出现。

样例 5

ababa
baba
3
5 5 3
7
1 13
2 5
3 6
5 10
6 13
9 13
1 3

2
1
0
1
1
0
0

样例 5 解释

拼接后得到 P= ababa+ababa+aba= ababaababaaba。目标串 baba 的两次出现分别从位置 $2,7$ 开始。区间 $[3,6]$ 虽然与第一次出现相交，却没有完整包含它，因此答案为 $0$。

数据范围

对于所有测试数据，保证：

• $2\leq |S|,|T|\leq 5\times10^5$；
• $1\leq n,q\leq 5\times10^5$；
• $1\leq a_i\leq |S|$；
• $1\leq l\leq r\leq\sum_{i=1}^{n}a_i$；
• $S,T$ 中只包含小写英文字母。

本题共有 $20$ 个独立计分的测试点，每个测试点 $5$ 分，共 $100$ 分。

测试点编号	$n,\ \lvert S\rvert,\ \lvert T\rvert$ 的上限	$q$ 的上限
$1\sim3$	$10^3$
$4\sim8$	$5\times10^4$
$9\sim10$	$5\times10^5$
$11\sim13$	$10^3$	$1.5\times10^5$
$14\sim16$	$1.5\times10^5$
$17\sim20$	$5\times10^5$