Description

Given a string $S$, each query provides two substrings $S[l_1, r_1]$ and $S[l_2, r_2]$. You need to count how many ways to split $S[l_1, r_1]$ such that $S[l_1, r_1] = A + B + C$ and $C + B^R + A = S[l_2, r_2]$. Here, $B^R$ means the reverse of string $B$, $+$ means string concatenation, and $S[l, r]$ means taking the $l$-th to the $r$-th characters of $S$. Strings $A$, $B$, and $C$ can be empty.

Input Format

The first line contains two positive integers $n$ and $m$, representing the length of $S$ and the number of queries.

The second line contains a string of length $n$ consisting of lowercase letters, representing $S$.

The next $m$ lines each contain four positive integers $l_1, r_1, l_2, r_2$, representing the query intervals. It is guaranteed that $r_1 - l_1 = r_2 - l_2$.

Output Format

Output $m$ lines, each containing one positive integer, representing the answer.

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

11
9
2
17

Hint

This problem uses bundled testdata.

For all testdata, it is guaranteed that $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$, and $r_1 - l_1 = r_2 - l_2$.

For Subtask $i$, the time limit is $i + 1$ seconds.

Translated by ChatGPT 5