Problem Background

Time Limit: 3s, Memory Limit: 162MB

Our lovers are merely borrowed names, soap bubbles blown with fantasy. Take this letter; you can make fiction a reality. I was originally moaning without purpose, aimlessly expressing love—now these wandering birds have a place to rest, as you can see from the letter. Take it—since it's not from the heart, the words are exceptionally pleasing. Take it, just do it...

Since the world will end on July 20th, as the savior, Takashi Mamimi must bring everyone back to the sky on the 19th.

It is now the evening of the 19th, and everyone is gathered on the rooftop of Building C, a total of n people.

In front of them is the final sky, the sky of终结.

Problem Description

Returning to the sky is a solemn event, so Takashi decides to have everyone do it in batches, assigning each person a lowercase letter 'a' to 'z' as a code.

A group of people within a certain range can return to the sky together if their codes, when rearranged, can form a palindrome. That is, this range can return to the sky.

Since Takashi is a person who likes to fantasize, he fantasizes about m ranges and wants to know how many sub-ranges within each range can return to the sky.

Because the end of the world is approaching, Takashi has many followers.

Input Format

The first line contains two numbers n and m.

The next line is a string of length n representing everyone's code.

The following m lines each contain two numbers l and r representing the ranges Takashi fantasizes about.

Output Format

m lines, each containing a number representing the answer.

Sample Input and Output

Sample Input #1

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

Sample Output #1

16
4
2
2
3
1

Sample Input #2

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

Sample Output #2

3
3
2
3
3
17

Sample Input #3

4 1
yuno
1 4

Sample Output #3

4

Notes

For 10% of the data, n, m <= 100.

For 30% of the data, n, m <= 2000.

For 100% of the data, n, m <= 60000.

The size of the character set varies.

After everyone returns to the sky, Ayame reveals a cold smile.

见题面 Input 部分

见题面 Output 部分