Longest Valid Prayer Word

Xiao Xi worships n gods and his belief in each god is represented by a lowercase letter. All the beliefs form a string s (indexed from 1). A prayer word is defined as any non-empty contiguous substring of s. A prayer word is considered valid if it appears at least twice (the occurrences are counted as long as their starting positions are different, overlapping is allowed).

However, due to distractions, only the substring of s in the interval \([l,r]\), i.e. \(s[l\dots r]\), is available. Xiao Xi will prepare for all possibilities. In particular, he will run q queries: for each query, given \(l\) and \(r\), determine the maximum length of a valid prayer word in \(s[l\dots r]\).

Formally, for a given substring \(s[l\dots r]\) (of length \(L=r-l+1\)), find the maximum \(k\) (\(1 \le k \le L\)) such that there exist two different starting positions \(i\) and \(j\) with \(l \le i < j \le r-k+1\) for which \(s[i \dots i+k-1] = s[j \dots j+k-1]\). If no such \(k\) exists, output 0.

Note: All formulas are rendered in \(\LaTeX\) format.

inputFormat

The first line of input contains two integers \(n\) and \(q\), where \(n\) is the length of the string and \(q\) is the number of queries.

The second line contains the string \(s\) of length \(n\) consisting of lowercase letters.

Each of the following \(q\) lines contains two space-separated integers \(l\) and \(r\) representing a query.

outputFormat

For each query, output a single integer, which is the maximum length of a valid prayer word in the given substring \(s[l\dots r]\). If no valid prayer word exists, output 0.

sample

5 3
ababa
1 5
2 3
2 5

3
0
2