#2059. 「TJOI / HEOI2016」字符串

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

输入格式

输入的第一行有两个正整数 n,m n, m ,分别表示字符串的长度和询问的个数。
接下来一行是一个长为 n n 的字符串。字符串中仅有小写英文字母。
接下来 m m 行,每行有四个数 a,b,c,d a, b, c, d ,表示询问 s[ab]s[a \ldots b] 的所有子串和 s[cd] 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

数据范围与提示

对于所有的数据,1n,m100000, ab, cd, 1a,b,c,dn1 \leq n, m \leq 100000, \ a \leq b, \ c \leq d, \ 1 \leq a, b, c, d \leq n