For her birthday, Jia Yuan's friend bought her a gift from an online store. The gift is inside a magical box. On the outside of the box, there is a string $s$ of length $n$ and $m$ questions. Jia Yuan must answer these $m$ questions correctly to open the box, get the gift, get a promotion and a raise, become a CEO, marry a rich and handsome person, and reach the pinnacle of her life.

Each question consists of four parameters $a, b, c, d$. You are asked to find the maximum length of the longest common prefix between any substring of $s[a..b]$ and the substring $s[c..d]$.

Jia Yuan is not good at solving such problems, so she is asking for your help. How can you help her?

Input

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

The next line contains a string of length $n$.

The next $m$ lines each contain four integers $a, b, c, d$, representing the query for the maximum length of the longest common prefix between any substring of $s[a..b]$ and the substring $s[c..d]$.

Output

For each query, output the answer.

Constraints

• For 10% of the data, $1 \le n, m \le 300$.
• For 40% of the data, $1 \le n, m \le 3,000$, and the string contains only 'a' and 'b'.
• For 100% of the data, $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$.

Examples

Input 1

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

Output 1

1
1
2
2
2

Input 2

5 5
ababa
1 1 2 2
2 3 1 1
1 2 2 3
1 3 3 5
1 3 2 4

Output 2

0
1
1
3
2