3600 - Complementary Words II

Created by Oreste Nillar Cambara
Added by Oreste (2016-03-30)
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 = |S|-1) 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 = |S|-1) 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 = |S|-1) 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 non-empty 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 <= |S|-1).
The first line of input contains a non-empty 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 <= |S|-1).
The first line of input contains a non-empty 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 <= |S|-1).

Output specification

For each query you must print the number of continuous sub-sequences that are complementary words in the interval A, B.
For each query you must print the number of continuous sub-sequences that are complementary words in the interval A, B.
The first line of input contains a non-empty 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 <= |S|-1).

Sample input

acecc
4
0 2
1 2
1 3
3 4

Sample output

6
3
5
3

Hint(s)