Description:


Input:


输入第1行,包含3个整数N,Q。Q代表询问组数。
第2行是字符串S。
接下来Q行,每行两个整数i和j。(1≤i≤j)。

Output:


输出共Q行,每行一个数表示每组询问的答案。如果不存在第i个子串或第j个子串,则输出-1。

Sample Input:


Sample Output:


题解:


如果你知道利用后缀数组求第k小子串这个题就是水题了.
其实求第k小子串很简单,每一个后缀对本质不同子串数的贡献等于 \(n-sa[i]-height[i]\) ,然后二分查找一下就可以了.
这个题就查询后求一遍LCP和LCS,反着建一遍后缀数组,然后一样一样的.

没有开long long卡了我好久啊~