Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Segment Occurrences

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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]$$$.

Input

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.

Output

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]$$$.

Examples

Input

10 3 4

codeforces

for

1 3

3 10

5 6

5 7

Output

0

1

0

1

Input

15 2 3

abacabadabacaba

ba

1 15

3 4

2 14

Output

4

0

3

Input

3 5 2

aaa

baaab

1 3

1 1

Output

0

0

Note

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

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/24/2019 04:25:10 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|