CF1016B.Segment Occurrences

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

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