题目描述

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

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

对于「鸡你太美」，ikun 们提出了 $q$ 个问题。每个问题都是如下的形式：

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

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

输入格式

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

第二行，一个长度为 $n$ 的仅包含小写字母的字符串 $S$，表示「鸡你太美」。

接下来 $q$ 行，每行四个正整数 $l_1,r_1,l_2,r_2$，表示一组 ikun 们的询问。

输出格式

共 $q$ 行，第 $i$ 行一个非正整数，表示第 $i$ 个询问的答案。

样例

10 4
jinitaimei
2 5 7 10
2 4 2 4
3 6 7 9
7 9 1 2

-1
-3
0
-1

• 第一组询问中 $S_A$=init，$S_B$=imei，符合条件的 $S_{CXK}$ 仅有优美度为 $0$ 的空串与优美度为 $-1$ 的 i，因此答案为 $-1$。
• 第二组询问中 $S_A$=ini，$S_B$=ini，符合条件的 $S_{CXK}$ 有优美度为 $0$ 的空串，优美度为 $-1$ 的 i，以及优美度为 $-3$ 的 ini，因此答案为 $-3$。
• 第三组询问中 $S_A$=nita，$S_B$=ime，符合条件的 $S_{CXK}$ 仅有优美度为 $0$ 的空串，因此答案为 $0$。
• 第四组询问中 $S_A$=ime，$S_B$=ji，符合条件的 $S_{CXK}$ 仅有优美度为 $0$ 的空串与优美度为 $-1$ 的 i，因此答案为 $-1$。

数据范围与提示

对于全部数据，$1\leq n\leq 2\times 10^5$，$1\leq q\leq 2\times 10^5$，$1\leq l_1\leq r_1\leq n$，$1\leq l_2\leq r_2\leq n$。