这是问题的困难版本。在此版本中$$$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$$$) — 字符串的长度和给定范围。
每个测试用例的第二行包含长度为$$$n$$$的字符串$$$s$$$,所有字符均为小写英文字母。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,输出 $$$r-l+1$$$ 值:$$$f_l,\dots,f_r$$$。
示例
输入 #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