Description

On Jiayuan’s birthday, her friends bought her a birthday gift from an online store. The gift is placed in a magic box. On the outside of the box there is a string $s$ of length $n$, and $m$ questions. Jiayuan must answer these $m$ questions correctly to open the box and get the gift, get promoted and receive a raise, become the CEO, marry a rich and handsome man, and reach the pinnacle of life.

Each question has four parameters $a,b,c,d$. Among all substrings of $s[a..b]$, what is the maximum possible length of the longest common prefix with $s[c..d]$? Jiayuan is not good at such problems, so she asks you for help. How would you help her?

Input Format

The first line contains two positive integers $n,m$, denoting the length of the string and the number of queries.

The next line contains a string of length $n$. Then there are $m$ lines, each containing four integers $a,b,c,d$, representing a query asking for the maximum length of the longest common prefix between any substring of $s[a..b]$ and $s[c..d]$.

Output Format

For each query, output the answer.

5 5
aaaaa
1 1 1 5
1 5 1 1
2 3 2 3
2 4 2 3
2 3 2 4

1
1
2
2
2

Hint

For $10\%$ of the testdata, $1 \le n,m \le 300$.

For $40\%$ of the testdata, $1 \le n,m \le 3{,}000$, and the string contains only a, b.

For $100\%$ of the testdata, $1 \le n,m \le 100{,}000$, the string contains only lowercase English letters, $a \le b$, $c \le d$, and $1 \le a,b,c,d \le n$.

Translated by ChatGPT 5