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?
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).
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.
7 1 acgabgc 0 6
4 2 xyyx 0 2 2 3
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.
Login to submit
This problem can be solved with Mo's Algorithm. Before reading the rest of the editorial, I'd like t...