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