题目描述
众所周知，全民制作幼儿园园龄两年半的蔡徐坤同学喜欢唱、跳、rap 和篮球。而「鸡你太美」是他的成名作。
「鸡你太美」是一个字符集为 Σ=a,…,zΣ=a,…,z 的长度为 nn 的字符串 SS。为了衡量「鸡你太美」的优美程度，我们给一个字符串定义其优美度。对于一个回文串，我
们定义其优美度为其子串长度的相反数。对于一个非回文串，我们定义其优美度为 00。例如，aabaa 的优美度为 −5−5，而 abcd 的优美度为 00。
对于「鸡你太美」，ikun 们提出了 qq 个问题。每个问题都是如下的形式：
你需要回答，在满足下列条件的 SS 的子串 SCXK中，优美度的最小值。需要注意的是，中，优美度的最小值。需要注意的是，SCXKSCXK中，优美度的最小值。需要注意的是，中，优美度的最小值。需要注意的是，SCXK 可以为空串。
ikun A 给出两个参数 l1,r1l1,r1，表示 ta 指定的「鸡你太美」子串 SA为为Sl1…r1。ikunA要求。ikunA要求SCXK必须是必须是SASA为为Sl1…r1。ikunA要求。ikunA要求SCXK必须是必须是SA 的一个前缀。空串是任意
一个串的前缀。
ikun B 给出两个参数 l2,r2l2,r2，表示 ta 指定的「鸡你太美」子串 SB为为Sl2…r2。ikunB要求。ikunB要求SCXK必须是必须是SBSB为为Sl2…r2。ikunB要求。ikunB要求SCXK必须是必须是SB 的一个后缀。空串是任意
一个串的后缀。
如果你不能回答 ikun 们的问题，ta 们将聚在一起开始讨论蔡徐坤。为了制止 ta 们的 cxk 行为，你不得不完成这道幼儿园唱歌题。
输入格式
第一行，两个正整数 n,qn,q，表示「鸡你太美」的长度和 ikun 们的问题数。
第二行，一个长度为 nn 的仅包含小写字母的字符串 SS，表示「鸡你太美」。
接下来 qq 行，每行四个正整数 l1,r1,l2,r2l1,r1,l2,r2，表示一组 ikun 们的询问。
输出格式
共 qq 行，第 ii 行一个非正整数，表示第 ii 个询问的答案。
