#1712. 幼儿园唱歌题

幼儿园唱歌题

题目描述

众所周知,全民制作幼儿园园龄两年半的蔡徐坤同学喜欢唱、跳、rap 和篮球。而「鸡你太美」是他的成名作。

「鸡你太美」是一个字符集为 Σ={a,,z}\Sigma=\{\tt{a},\dots,\tt{z}\} 的长度为 nn 的字符串 SS。为了衡量「鸡你太美」的优美程度,我们给一个字符串定义其优美度。对于一个回文串,我们定义其优美度为其子串长度的相反数。对于一个非回文串,我们定义其优美度00。例如,aabaa 的优美度为 5-5,而 abcd 的优美度为 00

对于「鸡你太美」,ikun 们提出了 qq 个问题。每个问题都是如下的形式:

  • 你需要回答,在满足下列条件的 SS 的子串 SCXKS_{CXK} 中,优美度的最小值。需要注意的是,SCXKS_{CXK} 可以为空串。
  • ikun A 给出两个参数 l1,r1l_1,r_1,表示 ta 指定的「鸡你太美」子串 SAS_ASl1r1S_{l_1\dots r_1}。ikun A 要求 SCXKS_{CXK} 必须是 SAS_A 的一个前缀。空串是任意一个串的前缀。
  • ikun B 给出两个参数 l2,r2l_2,r_2,表示 ta 指定的「鸡你太美」子串 SBS_BSl2r2S_{l_2\dots r_2}。ikun B 要求 SCXKS_{CXK} 必须是 SBS_B 的一个后缀。空串是任意一个串的后缀。

如果你不能回答 ikun 们的问题,ta 们将聚在一起开始讨论蔡徐坤。为了制止 ta 们的 cxk 行为,你不得不完成这道幼儿园唱歌题。

输入格式

第一行,两个正整数 n,qn,q,表示「鸡你太美」的长度和 ikun 们的问题数。

第二行,一个长度为 nn 的仅包含小写字母的字符串 SS,表示「鸡你太美」。

接下来 qq 行,每行四个正整数 l1,r1,l2,r2l_1,r_1,l_2,r_2,表示一组 ikun 们的询问。

输出格式

qq 行,第 ii 行一个非正整数,表示第 ii 个询问的答案。

样例

10 4
jinitaimei
2 5 7 10
2 4 2 4
3 6 7 9
7 9 1 2
-1
-3
0
-1
  • 第一组询问中 SAS_A=initSBS_B=imei,符合条件的 SCXKS_{CXK} 仅有优美度为 00 的空串与优美度为 1-1i,因此答案为 1-1
  • 第二组询问中 SAS_A=iniSBS_B=ini,符合条件的 SCXKS_{CXK} 有优美度为 00 的空串,优美度为 1-1i,以及优美度为 3-3ini,因此答案为 3-3
  • 第三组询问中 SAS_A=nitaSBS_B=ime,符合条件的 SCXKS_{CXK} 仅有优美度为 00 的空串,因此答案为 00
  • 第四组询问中 SAS_A=imeSBS_B=ji,符合条件的 SCXKS_{CXK} 仅有优美度为 00 的空串与优美度为 1-1i,因此答案为 1-1

数据范围与提示

子任务编号 分值 特殊限制
1 5 1n501\leq n\leq 501q101\leq q\leq 10
2 10 1n5001\leq n\leq 5001q5001\leq q\leq 500
3 15 1n20001\leq n\leq 20001q1041\leq q\leq 10^4
4 70 无特殊限制

对于全部数据,1n2×1051\leq n\leq 2\times 10^51q2×1051\leq q\leq 2\times 10^51l1r1n1\leq l_1\leq r_1\leq n1l2r2n1\leq l_2\leq r_2\leq n