Опытным участникам соревнований по спортивному программированию хорошо известна классическая задача о нахождении количества вхождений подстроки в строку. Обычно она формулируется так: дана строка-образец $$$s$$$ и строка $$$t$$$, требуется найти количество индексов, начиная с которых строка $$$s$$$ содержится в строке $$$t$$$.
К сожалению, для решения этой задачи уже придумано множество алгоритмов, поэтому сама по себе она может быть интересна только в качестве упражнения, но не олимпиадной задачи. Однако, как это часто бывает со стандартными задачами, её легко усложнить — представим, что нас интересуют не сами строки $$$s$$$ и $$$t$$$, а некоторые их подстроки $$$s[l_1 \ldots r_1]$$$ и $$$t[l_2 \ldots r_2]$$$.
Как вы уже, наверное, догадались, вам дано $$$q$$$ запросов, $$$i$$$-й из которых задаёт некоторые подстроки $$$\bar s = s[{l_1}_i \ldots {r_1}_i]$$$ и $$$\bar t = t[{l_2}_i \ldots {r_2}_i]$$$. Для каждого такого запроса необходимо посчитать количество вхождений строки $$$\bar s$$$ в строку $$$\bar t$$$.
Первая и вторая строки входных данных содержат строки $$$s$$$ и $$$t$$$ ($$$1 \le |s|, |t| \le 2 \cdot 10^5$$$) соответственно. Строки состоят из маленьких букв английского алфавита.
В третьей строке задано одно число $$$q$$$ ($$$1 \le q \le 5 \cdot 10^5$$$) — количество запросов.
Каждая из следующих $$$q$$$ строк содержит по четыре числа $$$l_1$$$, $$$r_1$$$, $$$l_2$$$ и $$$r_2$$$ ($$$1 \le l_1 \le r_1 \le |s|, 1 \le l_2 \le r_2 \le |t|$$$), описывающих очередной запрос.
Выведите $$$q$$$ чисел — ответы на запросы.
abb
ababababb
5
1 2 1 7
2 3 2 9
3 3 4 7
1 2 2 4
1 1 1 9
3
1
2
1
4
Рассмотрим запросы в первом примере. Для индексации позиций вхождения будем использовать изначальные позиции в строке $$$t$$$.
Тесты к этой задаче состоят из четырех подзадач. Баллы за каждую подзадачу ставятся только при прохождении всех тестов подзадачи и всех тестов необходимых подзадач.
