Status:  Past  Start:  20160409 10:00:00  End:  20160409 14:00:00 
Liga Cubana de Programación 2016 (Etapa III  OPEN)
Problem
3600  Complementary Words II
Created by  Oreste Nillar Cambara 
Added by  Oreste (20160330) 
Limits 
Total Time: 12000 MS

Test Time:
4000 MS
Memory: 512 MB  Output: 64 MB  Size:
9 KB

Enabled languages  
Available in 
Description
This time John has been playing with strings, he has discovered the palindromes strings, a palindrome string is one string that is read in the same way, from left to right and from right to left. John has made a small change to the definition and called the result complementary words.
A word S is complementary if for any pair (0 <= i, j < S and i + j = S1) the sum of the character values S[i] + S[j] is the same, and values for a, b, ..., z are 1, 2, ..., 26.
This time John has been playing with strings, he has discovered the palindromes strings, a palindrome string is one string that is read in the same way, from left to right and from right to left. John has made a small change to the definition and called the result complementary words.
A word S is complementary if for any pair (0 <= i, j < S and i + j = S1) the sum of the character values S[i] + S[j] is the same, and values for a, b, ..., z are 1, 2, ..., 26.
This time John has been playing with strings, he has discovered the palindromes strings, a palindrome string is one string that is read in the same way, from left to right and from right to left. John has made a small change to the definition and called the result complementary words.
A word S is complementary if for any pair (0 <= i, j < S and i + j = S1) the sum of the character values S[i] + S[j] is the same, and values for a, b, ..., z are 1, 2, ..., 26.
Input specification
The first line of input contains a nonempty string S (1 <= S <= 3000) consisting of lowercase letters. The second line is an integer (1 <= N <= 10^6) representing the number of queries to be performed, line 3, 4, ..., N + 2 contains two integers A, B (0 <= A,B <= S1).
The first line of input contains a nonempty string S (1 <= S <= 3000) consisting of lowercase letters. The second line is an integer (1 <= N <= 10^6) representing the number of queries to be performed, line 3, 4, ..., N + 2 contains two integers A, B (0 <= A,B <= S1).
The first line of input contains a nonempty string S (1 <= S <= 3000) consisting of lowercase letters. The second line is an integer (1 <= N <= 10^6) representing the number of queries to be performed, line 3, 4, ..., N + 2 contains two integers A, B (0 <= A,B <= S1).
Output specification
For each query you must print the number of continuous subsequences that are complementary words in the interval A, B.
For each query you must print the number of continuous subsequences that are complementary words in the interval A, B.
The first line of input contains a nonempty string S (1 <= S <= 3000) consisting of lowercase letters. The second line is an integer (1 <= N <= 10^6) representing the number of queries to be performed, line 3, 4, ..., N + 2 contains two integers A, B (0 <= A,B <= S1).
Sample input
acecc
4
0 2
1 2
1 3
3 4
Sample output
6
3
5
3
Hint(s)