Description

There are a total of $n$ gods that Xiao Xi wants to worship. Xiao Xi’s belief for each god can be represented by a lowercase letter. Putting them together forms a string $s$ indexed starting from $1$.

Xiao Xi needs prayer words to worship the gods. A prayer word is defined as a non-empty contiguous substring of $s$, and its length is the length of this substring. Since worshipping only requires Xiao Xi to be serious enough, a prayer word is considered valid as long as it appears at least twice.

Note: as long as the starting positions of the two occurrences are different, it is fine even if the two substrings overlap.

However, because her parents are also present, Xiao Xi’s prayer words may sometimes be interrupted, so only the string within the interval $[l,r]$ (i.e., $s[l\dots r]$) is valid. To be prepared, Xiao Xi will carefully prepare for all possible situations.

He will give $q$ queries. In each query, $l,r$ are given, and you need to ask for the length of the longest valid prayer word within the interval $[l,r]$.

Input Format

The first line contains two positive integers $n,q$.
The second line contains a string $s$ consisting of lowercase letters.
The next $q$ lines each contain two numbers $l,r$.

Output Format

Output $q$ lines. Each line outputs a non-negative integer, representing the length of the longest valid prayer word. If there is no valid prayer word, output $0$.

10 5
cdabababdc
3 7
2 8
5 10
6 10
1 4

3
4
2
1
0

Hint

Sample Explanation:

For the first query: the string in the interval is $\texttt{ababa}$, where the substring $\texttt{aba}$ appears twice, with length $3$.
For the second query: the string in the interval is $\texttt{dababab}$, where the substring $\texttt{abab}$ appears twice, with length $4$.
For the third query: the string in the interval is $\texttt{ababdc}$, where the substring $\texttt{ab}$ appears twice, with length $2$.
For the fourth query: the string in the interval is $\texttt{babdc}$, where the substring $\texttt{b}$ appears twice, with length $1$.
For the fifth query: the string in the interval is $\texttt{cdab}$, and no substring appears at least twice, so the answer is $0$.

Constraints:

For $5\%$ of the data, $n,q\le50$.
For $15\%$ of the data, $n,q\le200$.
For $30\%$ of the data, $n,q\le2\times10^3$.
For $40\%$ of the data, $n,q\le5\times10^3$.
For $65\%$ of the data, $n,q\le2\times 10^4$.
For another $5\%$ of the data, all characters are the same.
For $100\%$ of the data, $1 \le n\le5\times10^4$ and $1 \le q \le 10^5$.

Translated by ChatGPT 5