Филипп очень любит задачечки на строчечки. Он уже решил все известные ему задачечки, но этого ему было мало. Поэтому Филипп решил придумать свою собственную задачечку.
Для этого он взял строку \(t\) и набор из \(n\) строк \(s_1\), \(s_2\), \(s_3\), ..., \(s_n\). У Филиппа есть \(m\) запросов, в \(i\)-м из них Филипп хочет взять подстроку строки \(t\) с \(l_i\)-го по \(r_i\)-й символ, и посчитать число её подстрок, которые совпадают с какой-то строкой из набора. Более формально, Филипп хочет посчитать число пар позиций \(a\), \(b\), таких что \(l_i \le a \le b \le r_i\), и подстрока строки \(t\) с \(a\)-го по \(b\)-й символ совпадает с некоторой строкой \(s_j\) из набора.
Подстрокой строки \(t\) с \(a\)-го по \(b\)-й символ называется строка, полученная из \(t\) путём удаления \(a - 1\) символа из начала и \(|t| - b\) символами из конца, где \(|t|\) обозначает длину строки \(t\).
Филипп уже решил эту задачу, а сможете ли вы?
Выходные данные
В единственной строке выведите \(m\) целых чисел, \(i\)-е из них должно быть равно ответу на \(i\)-й запрос.
Примечание
В первом примере в первом запросе требуется у всей строки посчитать число подстрок, которые входят в набор. Со строкой «aba» совпадают подстроки \([1, 3]\) и \([4, 6]\). Со строкой «a» совпадают подстроки \([1, 1]\), \([3, 3]\), \([5, 5]\), \([7, 7]\). Со строкой «ac» совпадает подстрока \([3, 4]\). Всего получается, что 7 подстрок строки «abacaba» совпадают со строками из набора.
Во втором запросе от исходной строки берется подстрока с 1 по 3 позицию, это строка «aba». В неё строка «aba» входит 1 раз, строка «a» входит 2 раза и строка «ac» не входит ни одного раза как подстрока. В третьем запросе от исходной строки берется подстрока с 2 по 7 позицию, это строка «bacaba». В неё строка «aba» входит 1 раз, строка «a» входит 3 раза и строка «ac» входит 1 раз как подстрока.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 5
abacaba
aba
a
ac
1 7
1 3
2 7
2 5
4 5
|
7 3 5 3 1
|
|
2
|
4 4
abcdca
ab
ca
bcd
openolympiad
1 5
2 2
2 6
1 6
|
2 0 2 3
|