Background

Time limit $\texttt{3s}$, memory limit $\texttt{158.2MB}$.

Subarashiki Hibi.

Our lovers are just names we casually borrow, soap bubbles blown by imagination. Take the letter; you can turn make-believe into reality. I was lamenting without an illness, aimlessly pouring out love—now these drifting birds have a perch, as you can see in the letter. Take it—precisely because it isn’t from the heart, the words sound all the more charming. Take it; let’s do it this way....

Since the world will end on $7$ 月 $20$ 日, as the savior, Mamiya Takuji must let everyone return to the sky on $19$ 日.

It is already the evening of $19$ 日; everyone has gathered on the rooftop of Building C, $n$ people in total.

In front of them lies the Terminal Sky, the sky of the end.

Problem 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