[HEOI2016/TJOI2016]字符串

题目描述

佳媛姐姐过生日的时候,她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。箱子外边写了一个长为 $n$ 的字符串 $s$,和 $m$ 个问题。佳媛姐姐必须正确回答这 $m$ 个问题,才能打开箱子拿到礼物,升职加薪,出任 CEO,嫁给高富帅,走上人生巅峰。 每个问题均有 $a,b,c,d$ 四个参数,问你子串 $s[a..b]$ 的所有子串和 $s[c..d]$ 的最长公共前缀的长度的最大值是多少?佳媛姐姐并不擅长做这样的问题,所以她向你求助,你该如何帮助她呢?

输入输出格式

输入格式


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

输出格式


对于每一次询问,输出答案。

输入输出样例

输入样例 #1

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
1
2
2
2

说明

对于 $10\%$ 的数据,$1\le n,m\le 300$。 对于 $40\%$ 的数据,$1\le n,m\le 3,000$,字符串中仅有 `a`,`b`。 对于 $100\%$ 的数据,$1\le n,m\le 100,000$,字符串中仅有小写英文字母,$a\le b$,$c\le d$,$1\le a,b,c,d\le n$。