Chef and Balanced Strings

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef Smurf likes strings a lot but he likes balanced strings more. Smurf calls a string S a balanced string if and only if characters of strings S can be partitioned into two multisets M_{1} and M_{2} such that M_{1} = M_{2}.
For eg : Strings such as aabbcc, abcabc , baccba , abccba are all balanced strings as their characters can be partitioned into two multisets M_{1} and M_{2} such that M_{1} = M_{2} = {a,b,c} whereas strings such as aba, abc , abcdef, blablah are not balanced strings.
Today, Smurf found a special string P consisting of N lower case Latin letters. Smurf wants to make some queries about his string P.
Each of Smurf's query consists of 3 integers L R type. For a given query, Smurf wants to calculate this :
For all T_{s,e}, where T_{s,e} is balanced string such that starting index s and ending index e of a chosen string T_{s,e} satisfies L ≤ s < e ≤ R.
Note : T_{s,e} denotes the length of string T_{s,e}.
Just to make this problem little bit more interesting, given input is encoded. Instead of L and R in each query, you will be provided with two integers X and Y. Two keys A and B are used to decode the given input.
void decode(){
A = 0 ; // initialising first key
B = 0 ; // initialising second key
Q = input(); // number_of_queries;
while( Q  ) {
X = input();
Y = input();
type = input() ;
L = ( X + A ) % N + 1; // decoding L
R = ( Y + B ) % N + 1; // decoding R
// N is the length of the given string
if (L > R) {
// swap L and R
int T = L;
L = R;
R = T;
}
ans = solve(L,R,type); // calculate answer for current query
A = B; // updating key A
B = ans; // updating key B
}
}
Smurf cannot accomplish this task alone. Can you help him ?
Input
First line of the input contains a single integer T denoting the number of test cases. First line of each test case contains a string P denoting the chef's special string. Next line of the each test case contains a single integer Q denoting the number of chef's queries. Next Q lines of the each test case contains three space separated integers denoting X, Y and type respectively.
Output
For each of the chef's query, print the required answer.
Note
Two substrings T_{s1,e1} and T_{s2,e2} are considered to be different if either s_{1} != s_{2} or e_{1} != e_{2} where s_{1},e_{1} and s_{2},e_{2} are the starting and ending indices of string T_{1} and string T_{2} respectively.
Constraints
 1 ≤ T ≤ 10^{5}.
 1 ≤ P ≤ 10^{5}.
 1 ≤ Q ≤ 10^{5}.
 0 ≤ X,Y < P.
 type = { 0 , 1 , 2 }.
 sum of N over all test cases i.e SN does not exceed 10^{5}.
 sum of Q over all test cases i.e SQ does not exceed 10^{5}.
 All test files are strictly according to constraints.
Subtasks
 Subtask #1: 1 ≤ SN,SQ ≤ 500 , type = { 0, 1, 2 }. : ( 20 pts )
 Subtask #2: 1 ≤ SN,SQ ≤ 10^{4} , type = { 0, 1, 2 }. : ( 20 pts )
 Subtask #3: 1 ≤ SN,SQ ≤ 10^{5} , type = { 0 }. : ( 20 pts )
 Subtask #4: 1 ≤ SN,SQ ≤ 10^{5} , type = { 0, 1 }. : ( 20 pts )
 Subtask #5: 1 ≤ SN,SQ ≤ 10^{5} , type = { 0, 1, 2 }. : ( 20 pts )
Example
Input 1 cchheeff 5 0 1 0 0 2 1 7 5 2 0 7 0 1 1 2 Output 1 8 80 10 4
Explanation
After decoding queries will take the following form : 1 cchheeff 5 1 2 0 1 4 1 1 6 2 1 8 0 2 4 2Q1 : "cc" is the only balanced string. Type = 0 and therefore answer = 1.
Q2 : "cc" , "hh" , "cchh" are the only balanced strings. Type = 1 and therefore answer = 2 + 2 + 4 = 8.
Q3 : "cc" , "hh" , "ee" , "cchh" , "hhee" , "cchhee" are the only balanced strings. Type = 2 and therefore answer = 2^{2} + 2^{2} + 2^{2} + 4^{2} + 4^{2} + 6^{2}= 80.Warning
Large test data set, Prefer to use faster input/output methods .
Author:  ma5termind 
Tester:  kevinsogo 
Editorial  http://discuss.codechef.com/problems/CBAL 
Tags  ma5termind, may15, mediumhard, sqrtdecomp 
Date Added:  3032015 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions