CF2164H.PalindromePalindrome

We define the humor value of a string $t$ as the length of the longest palindrome string which occurs at least twice in it.

Formally, a string $p$ is humor with respect to $t$, if and only if both of the following conditions are met:

1. $p$ is a palindrome, and
2. there exist at least two different indices $i \in [1, |t| - |p| + 1]$, such that $t[i, i + |p| - 1] = p$.

The humor value of $t$ is defined as the maximum length among all humor strings with respect to $t$.

You are given a string $s$ of length $n$ which only contains lowercase Latin letters and $q$ queries. Each query contains two integers $l_i$, $r_i$, and you need to find the humor value of the string $s[l_i, r_i]$.

Here, $a[l, r]$ is defined as the string $a_l,a_{l+1},\ldots,a_r$.

我们定义字符串 $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$。

The first line contains two integers $n$, $q$ ($1\le n,q\le 5\cdot10^5$).

The second line contains a string $s$.

The next $q$ lines contain the description of queries. The $i$-th line contains two integers $l_i$, $r_i$ ($1\le l_i\le r_i\le n$).

第一行包含两个整数 $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$）。

On the $i$-th line, output the answer to the $i$-th query.

在第 $i$ 行输出第 $i$ 个查询的答案。

In the first query, the following palindrome strings occur at least twice: a,aa,aaa,aaaa,b,bb,bbb. The longest one is aaaa, so the humor value is $4$.

In the second query, one of the longest humor strings with respect to $s[2, 7]$ is aa.

在第一次查询中，以下回文字符串至少出现两次：a、aa、aaa、aaaa、b、bb、bbb。其中最长的是 aaaa，因此幽默值为 $4$。

在第二次查询中，关于子串 $s[2, 7]$ 的一个最长幽默字符串是 aa。