P8006 String Rearrangement in Phantom

有一字符串 $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$ 行，每行一个正整数表示答案。

**本题采用捆绑测试** | 子任务编号 | 分值 | 特殊限制 | | :----------: | :----------: | :----------:| | $0$ | $10$ | $1\le n,m\le 100$ | | $1$ | $10$ | $1\le n,m\le 500$ | | $2$ | $20$ | $1\le n,m\le 3000$ | | $3$ | $30$ | $1\le n,m\le 5\times 10^4$ | | $4$ | $30$ | $1\le n\le 2\times 10^5$，$1\le m\le 10^5$ | 对于所有数据，保证 $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$ 秒。