Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Gyanbaba's Admission Test 2

Limits: 3s, 512 MB

Gyanbaba, the wisest saint of the universe, has returned to the holy land of Chittagong Hill Tracts. Like last season, His Holiness is looking forward to spread his knowledge only to the chosen person. We all know his fondness for palindromes. This year he is again asking the applicants, who seek his holy knowledge, to solve a problem related to palindromes.

Gyanbaba gives all the applicants a string S, containing lowercase English letters only. He also gives them Q queries, each query is of the form l, r. The answer of Query(l, r) is the number of sub-strings of the string S[l, l+1, …, r], which can be permuted to create a palindrome.

Can you answer all the queries correctly and enroll as a murid (apprentice) of His Holiness?

Input

The first line of input contains two integers N (1 ≤ N ≤ 5*104) and Q (1 ≤ Q ≤ 5*104). The second line has a string S of length N, containing lowercase English letters only. The following Q lines, each contains two integers l and r (0 ≤ l ≤ r ≤ n-1).

Output

For each query, print the number of sub-strings of the string S[l, l+1, … , r], which can be permuted to create a palindrome, in separate lines.

Samples

InputOutput
7 1
acgabgc
0 6
8
InputOutput
4 2
xyyx
0 2
2 3
5
2

Explanation of Sample I/O

In first sample, the substrings formed by following pair of integers can create palindromes: (0, 0), (0, 6), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6). So the answer of query-1 is 8.

In second case, palindromes can be formed by permuting the following substrings: (0, 0), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 2), (3, 3). So the answer of query-1 is 5 and answer of query-2 is 2.

Author
Discussion
Submit

Login to submit