Longest Common Substring Query

You are given a string \( s \) of length \( n \) and \( m \) queries. The string \( s \) is written on the outside of a magical box containing a birthday gift. To open the box and claim the prize, you must answer all \( m \) queries correctly.

Each query consists of four integers \( a, b, c, d \). For a given query, let \( S_1 = s[a\ldots b] \) and \( S_2 = s[c\ldots d] \). Consider all possible substrings of \( S_1 \) and all possible substrings of \( S_2 \). For any two substrings \( u \) from \( S_1 \) and \( v \) from \( S_2 \), define their longest common prefix (LCP) as the maximum integer \( L \) such that the first \( L \) characters of \( u \) and \( v \) are identical. Your task for each query is to find the maximum possible LCP length among all valid pairs \( (u, v) \).

Note: This is equivalent to computing the length of the longest common substring between \( S_1 \) and \( S_2 \), because for any common substring \( x \) that appears in both \( S_1 \) and \( S_2 \), one can choose \( u = x \) and \( v = x \) so that \( \mathrm{LCP}(u,v) = |x| \).

Input Format:

• The first line contains two integers \( n \) and \( m \), where \( n \) is the length of the string \( s \) and \( m \) is the number of queries.
• The second line contains the string \( s \) consisting of lowercase English letters.
• The following \( m \) lines each contain four integers \( a, b, c, d \) representing a query.

Output Format:

• For each query, output a single integer on a new line representing the maximum length of the longest common prefix among all pairs of substrings from \( s[a\ldots b] \) and \( s[c\ldots d] \).

Constraints: It is guaranteed that the input sizes are small enough for a dynamic programming solution to pass.

inputFormat

The input begins with a line containing two integers \( n \) and \( m \). The next line contains the string \( s \) of length \( n \). Then \( m \) lines follow, each containing four integers \( a \), \( b \), \( c \), \( d \) separated by spaces.

outputFormat

For each query, output the maximum length of the longest common prefix (i.e. the longest common substring) between some substring of \( s[a\ldots b] \) and some substring of \( s[c\ldots d] \), each answer on a separate line.

sample

6 3
abcdef
1 3 2 4
1 6 1 6
2 4 4 6

2
6
1