Длиной наибольшего общего префикса двух строк \(s=s_1 s_2 \ldots s_n\) и \(t = t_1 t_2 \ldots t_m\) называется максимальное такое \(k \le \min(n, m)\), что строки \(s_1 s_2 \ldots s_k\) и \(t_1 t_2 \ldots t_k\) равны. Будем обозначать длину наибольшего общего префикса двух строк \(s\) и \(t\) как \(lcp(s,t)\).
Z-функция строки \(s_1 s_2 \dots s_n\) — это последовательность чисел \(z_1, z_2, \ldots, z_n\), где \(z_i = lcp(s_1 s_2 \ldots s_n,\ \ s_i s_{i+1} \dots s_n)\). Ж-функцией строки назовем величину \(z_1 + z_2 + \ldots + z_n\).
Вам дана строка \(s=s_1 s_2 \ldots s_n\) и \(q\) запросов. Запрос с номером \(i\) описывается двумя числами \(l_i\) и \(r_i\), где \(1 \le l_i \le r_i \le n\). В качестве ответа на запрос посчитайте значение Ж-функции строки \(s_{l_i} s_{l_i +1} \ldots s_{r_i}\).
Выходные данные
Для каждого запроса выведите единственное число — Ж-функцию соответствующей подстроки.
Примечание
В первом примере содержатся четыре запроса:
- первый запрос соответствует строке bb, Ж-функция которой равна \(2 + 1 = 3\);
- второй запрос соответствует строке abb, Ж-функция которой равна \(3 + 0 + 0 = 3\);
- третий запрос соответствует строке b, Ж-функция которой равна 1;
- четвертый запрос соответствует строке abbd, Ж-функция которой равна \(4 + 0 + 0 + 0= 4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
abbd
4
2 3
1 3
3 3
1 4
|
3
3
1
4
|
|
2
|
bbaaa
5
2 4
1 5
1 5
3 3
1 2
|
3
6
6
1
3
|