Заданы две строки \(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]\).
Выходные данные
Выведите \(q\) строк — в \(i\)-й строке должен содержаться ответ на \(i\)-й запрос, то есть количество вхождений строки \(t\) в подстроку \(s[l_i..r_i]\).
Примечание
В первом примере запросами является подстроки: «cod», «deforces», «fo» и «for», соответственно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 3 4
codeforces
for
1 3
3 10
5 6
5 7
|
0
1
0
1
|
|
2
|
15 2 3
abacabadabacaba
ba
1 15
3 4
2 14
|
4
0
3
|
|
3
|
3 5 2
aaa
baaab
1 3
1 1
|
0
0
|