Поиск подподстроки в подстроке

문제

Опытным участникам соревнований по спортивному программированию хорошо известна классическая задача о нахождении количества вхождений подстроки в строку. Обычно она формулируется так: дана строка-образец $ss$ и строка $tt$, требуется найти количество индексов, начиная с которых строка $ss$ содержится в строке $tt$.

К сожалению, для решения этой задачи уже придумано множество алгоритмов, поэтому сама по себе она может быть интересна только в качестве упражнения, но не олимпиадной задачи. Однако, как это часто бывает со стандартными задачами, её легко усложнить --- представим, что нас интересуют не сами строки $ss$ и $tt$, а некоторые их подстроки $s[l_1\dots r_1]s[l\_1\; \backslash ldots\; r\_1]$ и $t[l_2\dots r_2]t[l\_2\; \backslash ldots\; r\_2]$.

Как вы уже, наверное, догадались, вам дано $qq$ запросов, $ii$-й из которых задаёт некоторые подстроки $\bar{s}=s[{l_1}_i\dots {r_1}_i]\backslash bar\; s\; =\; s[\{l\_1\}\_i\; \backslash ldots\; \{r\_1\}\_i]$ и $\bar{t}=t[{l_2}_i\dots {r_2}_i]\backslash bar\; t\; =\; t[\{l\_2\}\_i\; \backslash ldots\; \{r\_2\}\_i]$. Для каждого такого запроса необходимо посчитать количество вхождений строки $\bar{s}\backslash bar\; s$ в строку $\bar{t}\backslash bar\; t$.

입력

Первая и вторая строки входных данных содержат строки $ss$ и $tt$ ($1\le \mathrm{\mid }s\mathrm{\mid },\mathrm{\mid }t\mathrm{\mid }\le 2\cdot {10}^{5}1\; \backslash le\; |s|,\; |t|\; \backslash le\; 2\; \backslash cdot\; 10^5$) соответственно. Строки состоят из маленьких букв английского алфавита.

В третьей строке задано одно число $qq$ ($1\le q\le 5\cdot {10}^{5}1\; \backslash le\; q\; \backslash le\; 5\; \backslash cdot\; 10^5$) --- количество запросов.

Каждая из следующих $qq$ строк содержит по четыре числа $l_{1}l\_1$, $r_{1}r\_1$, $l_{2}l\_2$ и $r_{2}r\_2$ ($1\le l_1\le r_1\le \mathrm{\mid }s\mathrm{\mid },1\le l_2\le r_2\le \mathrm{\mid }t\mathrm{\mid }1\; \backslash le\; l\_1\; \backslash le\; r\_1\; \backslash le\; |s|,\; 1\; \backslash le\; l\_2\; \backslash le\; r\_2\; \backslash le\; |t|$), описывающих очередной запрос.

출력

Выведите $qq$ чисел --- ответы на запросы.

힌트

Рассмотрим запросы в первом примере. Для индексации позиций вхождения будем использовать изначальные позиции в строке $tt$.

1. $\bar{s}=ab,\bar{t}=abababa\backslash bar\; s\; =\; ab,\; \backslash bar\; t\; =\; abababa$. $\bar{s}\backslash bar\; s$ входит в $\bar{t}\backslash bar\; t$, начиная с индексов $[1,3,5][1,\; 3,\; 5]$.
2. $\bar{s}=bb,\bar{t}=babababb\backslash bar\; s\; =\; bb,\; \backslash bar\; t\; =\; babababb$. $\bar{s}\backslash bar\; s$ входит в $\bar{t}\backslash bar\; t$, начиная с индекса $[8][8]$.
3. $\bar{s}=b,\bar{t}=baba\backslash bar\; s\; =\; b,\; \backslash bar\; t\; =\; baba$. $\bar{s}\backslash bar\; s$ входит в $\bar{t}\backslash bar\; t$, начиная с индексов $[4,6][4,\; 6]$.
4. $\bar{s}=ab,\bar{t}=bab\backslash bar\; s\; =\; ab,\; \backslash bar\; t\; =\; bab$. $\bar{s}\backslash bar\; s$ входит в $\bar{t}\backslash bar\; t$, начиная с индекса $[3][3]$.
5. $\bar{s}=a,\bar{t}=ababababb\backslash bar\; s\; =\; a,\; \backslash bar\; t\; =\; ababababb$. $\bar{s}\backslash bar\; s$ входит в $\bar{t}\backslash bar\; t$, начиная с индексов $[1,3,5,7][1,\; 3,\; 5,\; 7]$.