B'This is the hard version of the problem. In this version l <= r . You are given a string s . For a fixed k , consider a division of s into exactly k continuous substrings w_1, ... ,w_k . Let f_k be the maximal possible LCP(w_1, ... ,w_k) among all divisions. LCP(w_1, ... ,w_m) is the length of the Longest Common Prefix of the strings w_1, ... ,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}, ... ,f_r . The first line contains a single integer t ( 1 <= t <= 10^4 ) -- the number of test cases. The first line of each test case contains two integers n , l , r ( 1 <= l <= r <= n <= 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 . For each test case, output r-l+1 values: f_l, ... ,f_r . '...