G2. Деление + LCP (сложная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это cложная версия задачи. В этой версии $$$l\le r$$$.

Дана строка $$$s$$$. Для фиксированного $$$k$$$ рассмотрим деление $$$s$$$ на ровно $$$k$$$ непрерывных подстрок $$$w_1,\dots,w_k$$$. Пусть $$$f_k$$$ — максимально возможное $$$LCP(w_1,\dots,w_k)$$$ среди всех делений.

$$$LCP(w_1,\dots,w_m)$$$ — это длина самого длинного общего префикса строк $$$w_1,\dots,w_m$$$.

Например, если $$$s=abababcab$$$ и $$$k=4$$$, то возможное деление $$$\color{red}{ab}\color{blue}{ab}\color{orange}{abc}\color{green}{ab}$$$. $$$LCP(\color{red}{ab},\color{blue}{ab},\color{orange}{abc},\color{green}{ab})$$$ равно $$$2$$$, так как $$$ab$$$ — самый длинный общий префикс этих четырех строк. Обратите внимание, что каждая подстрока состоит из непрерывного сегмента символов, и каждый символ принадлежит ровно одной подстроке.

Ваша задача — найти $$$f_l,f_{l+1},\dots,f_r$$$.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого теста содержит три целых числа $$$n$$$, $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n \le 2 \cdot 10^5$$$) — длина строки и заданный диапазон.

Вторая строка каждого набора содержит строку $$$s$$$ из $$$n$$$ символов, все символы — строчные буквы английского алфавита.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2\cdot 10^5$$$.

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

Для каждого набора входных данных выведите $$$r-l+1$$$ значений: $$$f_l,\dots,f_r$$$.

Пример
Входные данные
7
3 1 3
aba
3 2 3
aaa
7 1 5
abacaba
9 1 6
abababcab
10 1 10
aaaaaaawac
9 1 9
abafababa
7 2 7
vvzvvvv
Выходные данные
3 1 0 
1 1 
7 3 1 1 0 
9 2 2 2 0 0 
10 3 2 1 1 1 1 1 0 0 
9 3 2 1 1 0 0 0 0 
2 2 1 1 1 0