我们定义 幽默值 字符串 $$$t$$$ 的 作为其中至少出现两次的最长回文字符串的长度。
形式上,字符串 $$$p$$$ 是 关于$$$t$$$的幽默,当且仅当满足以下两个条件时:
- $$$p$$$ 是回文,并且
- 存在 至少两个不同的 索引 $$$i \in [1, |t| - |p| + 1]$$$,使得 $$$t[i, i + |p| - 1] = p$$$。 $$$t$$$ 的
的 幽默值 字符串 $$$t$$$ 的 被定义为所有长度中的最大长度 幽默 字符串 关于 $$$t$$$.
给您一个长度为 $$$n$$$ 的字符串 $$$s$$$,其中仅包含小写拉丁字母和 $$$q$$$ 查询。每个查询包含两个整数$$$l_i$$$、$$$r_i$$$,需要找到字符串$$$s[l_i, r_i]$$$的幽默值。
这里,$$$a[l, r]$$$ 被定义为字符串 $$$a_l,a_{l+1},\ldots,a_r$$$。
输入
第一行包含两个整数 $$$n$$$、$$$q$$$ ($$$1\le n,q\le 5\cdot10^5$$$)。
第二行包含字符串 $$$s$$$。
接下来的 $$$q$$$ 行包含查询的描述。第 $$$i$$$ 行包含两个整数 $$$l_i$$$、$$$r_i$$$ ($$$1\le l_i\le r_i\le n$$$)。
输出
在第 $$$i$$$ 行上,输出第 $$$i$$$ 查询的答案。
示例
输入复制
12 6aaaabbbbaaaa1 122 73 104 75 94 5
输出复制
4 2 3 2 3 0
注意
在第一个查询中,以下回文字符串至少出现两次: a、aa、aaa、aaaa、b、bb、bbb。最长的是 啊啊啊,所以 幽默值 字符串 $$$t$$$ 的 是 $$$4$$$。
在第二个查询中,最长的查询之一 幽默 相对于 $$$s[2, 7]$$$ 的字符串是 aa.