题目描述

有一字符串 $S$，每次询问两串 $S[l_1,r_1]$，$S[l_2,r_2]$，问有多少划分方式使得 $S[l_1,r_1]=A+B+C$，$C+B^R+A=S[l_2,r_2]$。其中 $B^R$ 表示 $B$ 串的翻转，$+$ 表示字符串的拼接，$S[l,r]$ 表示提取串 $S$ 的第 $l$ 到第 $r$ 个字符。$A,B,C$ 可以为空。

输入格式

第一行两个正整数 $n$ 和 $m$ 表示 $S$ 的长度和询问数。

第二行一个长度为 $n$ 的小写字母组成的字符串表示 $S$。

接下来 $m$ 行，每行四个正整数 $l_1,r_1,l_2,r_2$ 表示询问区间，保证 $r_1-l_1=r_2-l_2$。

输出格式

$m$ 行，每行一个正整数表示答案。

10 4
aabbaabbaa
1 6 5 10
3 6 5 8
1 3 5 7
1 10 1 10

11
9
2
17

提示

本题采用捆绑测试

对于所有数据，保证 $1\le n\le 2\times 10^5$，$1\le m\le 10^5$，$1\le l_1\le r_1\le n$，$1\le l_2\le r_2\le n$，$r_1-l_1=r_2-l_2$。

对于编号为 $i$ 的 Subtask，其时限为 $i+1$ 秒。