P4094 [HEOI2016/TJOI2016] 字符串

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

无

无

对于 $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$。