Segment Occurrences

有长度为 $n$ 的串 $a$,长度为 $m$ 的串 $b$，共 $q$ 次询问，每次询问 $a$ 在 $l$ 到 $r$ 区间中有多少个子串等于 $b$。

You are given two strings $ s $ and $ t $ , both consisting only of lowercase Latin letters. The substring $ s[l..r] $ is the string which is obtained by taking characters $ s_l, s_{l + 1}, \dots, s_r $ without changing the order. Each of the occurrences of string $ a $ in a string $ b $ is a position $ i $ ( $ 1 \le i \le |b| - |a| + 1 $ ) such that $ b[i..i + |a| - 1] = a $ ( $ |a| $ is the length of string $ a $ ). You are asked $ q $ queries: for the $ i $ -th query you are required to calculate the number of occurrences of string $ t $ in a substring $ s[l_i..r_i] $ .

The first line contains three integer numbers $ n $ , $ m $ and $ q $ ( $ 1 \le n, m \le 10^3 $ , $ 1 \le q \le 10^5 $ ) — the length of string $ s $ , the length of string $ t $ and the number of queries, respectively. The second line is a string $ s $ ( $ |s| = n $ ), consisting only of lowercase Latin letters. The third line is a string $ t $ ( $ |t| = m $ ), consisting only of lowercase Latin letters. Each of the next $ q $ lines contains two integer numbers $ l_i $ and $ r_i $ ( $ 1 \le l_i \le r_i \le n $ ) — the arguments for the $ i $ -th query.

Print $ q $ lines — the $ i $ -th line should contain the answer to the $ i $ -th query, that is the number of occurrences of string $ t $ in a substring $ s[l_i..r_i] $ .

10 3 4
codeforces
for
1 3
3 10
5 6
5 7

0
1
0
1

15 2 3
abacabadabacaba
ba
1 15
3 4
2 14

4
0
3

3 5 2
aaa
baaab
1 3
1 1

0
0

In the first example the queries are substrings: "cod", "deforces", "fo" and "for", respectively.