题目描述
佳媛姐姐过生日的时候,她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。箱子外边写了一个长为 n 的字符串 s,和 m 个问题。佳媛姐姐必须正确回答这 m 个问题,才能打开箱子拿到礼物,升职加薪,出任 CEO,嫁给高富帅,走上人生巅峰。每个问题均有 a, b, c, d 四个参数,问你子串 $s[a \ldots b]$ 的所有子串和$ s[c \ldots d]$ 的最长公共前缀的长度的最大值是多少?佳媛姐姐并不擅长做这样的问题,所以她向你求助,你该如何帮助她呢?
输入格式
输入的第一行有两个正整数 n, m,分别表示字符串的长度和询问的个数。
接下来一行是一个长为 n 的字符串。字符串中仅有小写英文字母。
接下来 m 行,每行有四个数 a, b, c, d,表示询问 $s[a \ldots b]$ 的所有子串和$ s[c \ldots 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数据范围与提示
对于所有的数据,$1\le n,m\le 100000,a\le b,c\le d,1\le a,b,c,d\le n $