CFCF2164H.PalindromePalindrome

我们定义字符串 $t$ 的幽默值为：在 $t$ 中至少出现两次的最长回文子串的长度。

具体地，对于一个字符串 $t$，只有当以下两个条件同时满足时，字符串 $p$ 才称为 $t$ 的幽默字符串：

1. $p$ 是回文串；
2. 存在至少两个不同的下标 $i \in [1, |t| - |p| + 1]$，使得 $t[i, i + |p| - 1] = p$。

字符串 $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\times10^5$）。

第二行包含一个字符串 $s$。

接下来的 $q$ 行，每行包含两个整数 $l_i$、$r_i$（$1\le l_i\le r_i\le n$），表示一次询问。

对于第 $i$ 个询问，输出一行答案。

对于第一个询问，下列回文串至少出现了两次：a、aa、aaa、aaaa、b、bb、bbb。最长的是 aaaa，所以幽默值为 $4$。

对于第二个询问，$s[2, 7]$ 的最长幽默字符串之一是 aa。