B. Вхождения в отрезках
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Заданы две строки $$$s$$$ и $$$t$$$, состоящие только из строчных латинских букв.

Подстрока $$$s[l..r]$$$ — это такая строка, которая получается путем взятия $$$s_l, s_{l + 1}, \dots, s_r$$$ без изменения порядка.

Каждое вхождение строки $$$a$$$ в строку $$$b$$$ — это такая позиция $$$i$$$ ($$$1 \le i \le |b| - |a| + 1$$$), что $$$b[i..i + |a| - 1] = a$$$ ($$$|a|$$$ — это длина строки $$$a$$$).

Вам приходят $$$q$$$ запросов: для $$$i$$$-го запроса необходимо посчитать количество вхождений строки $$$t$$$ в подстроку $$$s[l_i..r_i]$$$.

Входные данные

В первой строке записаны три целых числа $$$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]$$$.

Примеры
Входные данные
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
Примечание

В первом примере запросами является подстроки: «cod», «deforces», «fo» и «for», соответственно.