311308: CF1968G2. Division + LCP (hard version)

G2. Division + LCP (hard version)time limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

This is the hard version of the problem. In this version $l\le r$.

You are given a string $s$. For a fixed $k$, consider a division of $s$ into exactly $k$ continuous substrings $w_1,\dots,w_k$. Let $f_k$ be the maximal possible $LCP(w_1,\dots,w_k)$ among all divisions.

$LCP(w_1,\dots,w_m)$ is the length of the Longest Common Prefix of the strings $w_1,\dots,w_m$.

For example, if $s=abababcab$ and $k=4$, a possible division is $\color{red}{ab}\color{blue}{ab}\color{orange}{abc}\color{green}{ab}$. The $LCP(\color{red}{ab},\color{blue}{ab},\color{orange}{abc},\color{green}{ab})$ is $2$, since $ab$ is the Longest Common Prefix of those four strings. Note that each substring consists of a continuous segment of characters and each character belongs to exactly one substring.

Your task is to find $f_l,f_{l+1},\dots,f_r$.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$, $l$, $r$ ($1 \le l \le r \le n \le 2 \cdot 10^5$) — the length of the string and the given range.

The second line of each test case contains string $s$ of length $n$, all characters are lowercase English letters.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, output $r-l+1$ values: $f_l,\dots,f_r$.

ExampleInput

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

Output

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 

题目大意：
这是一个难题的困难版本。在这个版本中，给定 l≤r。给你一个字符串 s。对于固定的 k，考虑将 s 划分为恰好 k 个连续的子字符串 w_1,…,w_k。定义 f_k 为所有划分中 LCP(w_1,…,w_k) 的最大可能值。LCP(w_1,…,w_m) 是字符串 w_1,…,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},…,f_r。

输入数据格式：
第一行包含一个整数 t (1≤t≤10^4) —— 测试用例的数量。
每个测试用例的第一行包含三个整数 n, l, r (1≤l≤r≤n≤2⋅10^5) —— 字符串的长度和给定的范围。
每个测试用例的第二行包含一个长度为 n 的字符串 s，所有字符都是小写英文字母。
保证所有测试用例的 n 之和不超过 2⋅10^5。

输出数据格式：
对于每个测试用例，输出 r-l+1 个值：f_l,…,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题目大意： 这是一个难题的困难版本。在这个版本中，给定 l≤r。给你一个字符串 s。对于固定的 k，考虑将 s 划分为恰好 k 个连续的子字符串 w_1,…,w_k。定义 f_k 为所有划分中 LCP(w_1,…,w_k) 的最大可能值。LCP(w_1,…,w_m) 是字符串 w_1,…,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},…,f_r。 输入数据格式： 第一行包含一个整数 t (1≤t≤10^4) —— 测试用例的数量。 每个测试用例的第一行包含三个整数 n, l, r (1≤l≤r≤n≤2⋅10^5) —— 字符串的长度和给定的范围。 每个测试用例的第二行包含一个长度为 n 的字符串 s，所有字符都是小写英文字母。 保证所有测试用例的 n 之和不超过 2⋅10^5。 输出数据格式： 对于每个测试用例，输出 r-l+1 个值：f_l,…,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