Опытным участникам соревнований по спортивному программированию хорошо известна классическая задача о нахождении количества вхождений подстроки в строку. Обычно она формулируется так: дана строка-образец \(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\).