题目描述

对于一个 长度为 $n$ 的字符串 $s$，将 $s$ 的 本质不同的所有字串按字典序从小到大 排序。

比如串 ababa，共有 $9$ 个本质不同的字串，按要求排序后得到：

我们定义两个子串 $s[l...r]$ 和 $s[p...q]$ 的相似程度为 $f = a^2 + b^2$ 的最大值，其中 $a,b$ 满足：

• $s[l...l+a-1] = s[p...p+a-1]$，$s[r-b+1...r] = s[q-b+1...q]$，$0 \leq a \leq r - l + 1$，$0 \leq b \leq q - p + 1$。

接下来，我们要询问的是，排序后的第 $i$ 个子串和第 $j$ 个子串的相似程度是多少。

输入格式

输入第 $1$ 行，包含 $3$ 个整数 $n,Q$。$Q$ 代表询问组数。

第 $2$ 行是字符串 $s$。

接下来 $Q$ 行，每行两个整数 $i$ 和 $j$（$1 \leq i \leq j$）。

输出格式

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

5 3
ababa
3 5
5 9
8 10

18
16
-1

样例说明

• 第1组询问：两个子串是 aba,ababa。$f = 3^2 + 3^2 = 18$。
• 第2组询问：两个子串是 ababa,baba。$f = 0^2 + 4^2 = 16$。
• 第3组询问：不存在第 $10$ 个子串，输出 $-1$。

数据规模与约定

• 对于 $100\%$ 的数据，$0 \leq n \leq 10^5$，$0 \leq Q \leq 10^5$，字符串只由小写字母 a ~ z 组成。

题目来源

后缀数组+二分+RMQ