题目描述

佳媛姐姐过生日的时候，她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。
箱子外边写了一个长为 $n$ 的字符串 $s$ 和 $m$ 个问题。
佳媛姐姐必须正确回答这 $m$ 个问题，才能打开箱子拿到礼物，升职加薪，出任CEO，嫁给高富帅，走上人生巅峰。

每个问题均有 $a,b,c,d$ 四个参数，问你子串 $s[a \dots b]$ 的所有子串和 $s[c \dots d]$ 的最长公共前缀的长度的最大值是多少？

佳媛姐姐并不擅长做这样的问题，所以她向你求助，你该如何帮助她呢？

输入格式

第一行输入两个正整数 $n,m$，分别表示字符串的长度和询问的个数。
第二行输入一个长为 $n$ 的字符串 $s$。 接下来 $m$ 行，每行有 $4$ 个数 $a,b,c,d$，表示询问$s[a \dots b]$ 的所有子串和 $s[c \dots d]$ 的最长公共前缀的长度的最大值。

输出格式

对于每一次询问，输出一行表示答案。

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

数据规模与约定

对于 $100\%$ 的数据，$1\leq n,m \leq 10^5$。

保证字符串中仅含有小写英文字母，$a\leq b$，$c \leq d$，$1 \leq a,b,c,d \leq n$。