给定两个字符串 $$$s$$$ 和 $$$t$$$,两者均仅包含小写拉丁字母。
子串$$$s[l..r]$$$ 是字符$$$s_l, s_{l + 1}, \dots, s_r$$$ 不改变顺序得到的字符串。
字符串 $$$b$$$ 中字符串 $$$a$$$ 的每次出现都是一个位置 $$$i$$$ ($$$1 \le i \le |b| - |a| + 1$$$),使得 $$$b[i..i + |a| - 1] = a$$$ ($$$|a|$$$ 是字符串 $$$a$$$ 的长度)。
系统会向您询问 $$$q$$$ 查询:对于第 $$$i$$$ 查询,您需要计算子字符串 $$$s[l_i..r_i]$$$ 中字符串 $$$t$$$ 的出现次数。
输入
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$1 \le n, m \le 10^3$$$, $$$1 \le q \le 10^5$$$) — 分别是字符串 $$$s$$$ 的长度、字符串 $$$t$$$ 的长度和查询次数。
第二行是字符串 $$$s$$$ ($$$|s| = n$$$),仅由小写拉丁字母组成。
第三行是字符串 $$$t$$$ ($$$|t| = m$$$),仅由小写拉丁字母组成。
接下来的 $$$q$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — 第 $$$i$$$ 查询的参数。
输出
打印 $$$q$$$ 行 — 第 $$$i$$$ 行应包含第 $$$i$$$ 查询的答案,即字符串 $$$t$$$ 在子字符串 $$$s[l_i..r_i]$$$ 中出现的次数。
示例
输入 #1
10 3 4 codeforces for 1 3 3 10 5 6 5 7
输出 #1
0 1 0 1
输入 #2
15 2 3 abacabadabacaba ba 1 15 3 4 2 14
输出 #2
4 0 3
输入 #3
3 5 2 aaa baaab 1 3 1 1
输出 #3
0 0
注意
在第一个示例中,查询分别是子字符串:“cod”、“deforces”、“fo”和“for”。