F. Ж-функция
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Длиной наибольшего общего префикса двух строк $$$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}$$$.

Входные данные

Первая строка входных данных содержит строку $$$s$$$, состоящую из строчных букв английского алфавита ($$$1 \leq |s| \leq 200\,000$$$). Следующая строка входных данных содержит целое число $$$q$$$ — количество запросов ($$$1 \leq q \leq 200\,000$$$). Каждая из следующих $$$q$$$ строк содержит два целых числа $$$l_i$$$ и $$$r_i$$$, которые описывают запрос с номером $$$i$$$ ($$$1 \leq l_i \leq r_i \leq |s|$$$).

Выходные данные

Для каждого запроса выведите единственное число — Ж-функцию соответствующей подстроки.

Примеры
Входные данные
abbd
4
2 3
1 3
3 3
1 4
Выходные данные
3
3
1
4
Входные данные
bbaaa
5
2 4
1 5
1 5
3 3
1 2
Выходные данные
3
6
6
1
3
Примечание

В первом примере содержатся четыре запроса:

  • первый запрос соответствует строке bb, Ж-функция которой равна $$$2 + 1 = 3$$$;
  • второй запрос соответствует строке abb, Ж-функция которой равна $$$3 + 0 + 0 = 3$$$;
  • третий запрос соответствует строке b, Ж-функция которой равна 1;
  • четвертый запрос соответствует строке abbd, Ж-функция которой равна $$$4 + 0 + 0 + 0= 4$$$.