划分与最长公共前缀（困难版）

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

给定字符串 $s$。对固定的 $k$，把 $s$ 划分成恰好 $k$ 个连续非空子串 $w_1,\ldots,w_k$，令 $f_k$ 为这些子串的最长公共前缀长度的最大可能值。

给定 $l,r$，求 $f_l,f_{l+1},\ldots,f_r$。

输入格式

第一行是测试组数 $t$。每组第一行包含 $n,l,r$，第二行是长度为 $n$ 的小写字符串 $s$。

输出格式

每组输出 $r-l+1$ 个整数。

样例输入 1

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

样例输出 1

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

数据范围

$1\le t\le10^4$，$1\le l\le r\le n\le2\cdot10^5$，所有测试组的 $n$ 之和不超过 $2\cdot10^5$。