Description

Returning to the sky is a solemn matter, so Takuji decides to proceed in batches, giving each person a lowercase letter $\texttt{a}\sim\texttt{z}$ as an identifier.

If a contiguous interval of people satisfies that their identifiers, after reordering, can form a palindrome, then they may return to the sky together; that is, this interval can return to the sky.

Because Takuji is fond of delusions, he imagines $m$ intervals; for each, he wants to know how many subintervals within it can return to the sky.

Since the end of the world is coming, Takuji has many followers.

Input Format

The first line contains two integers $n, m$.

The next line contains a string of length $n$ representing each person’s identifier.

Then follow $m$ lines; each line contains two integers $l, r$, representing one of Takuji’s imagined intervals.

Output Format

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

6 6
zzqzzq
1 6
2 4
3 4
2 3
4 5
1 1

16
4
2
2
3
1

6 6
aaabbb
1 2
2 3
3 4
4 5
5 6
1 6

3
3
2
3
3
17

4 1
yuno
1 4

4

Hint

For $10\%$ of the testdata, $n, m \le 100$.

For $30\%$ of the testdata, $n, m \le 2000$.

For $100\%$ of the testdata, $n, m \le 60000$.

The character set size varies across the testdata.

After everyone returns to the sky, Ayana reveals a chilling smile.

Translated by ChatGPT 5