Valentine and Queries

All submissions for this problem are available.
Valentines is coming after Q days and Tappu desperately needs to impress his girlfriend Kannu.
In order to test the extent of Tappu's love for her, Kannu gives Tappu a string S[1.....N] of length N .
On the i^{ th} day of the Q days, she asks him about the number of substrings in the string S[L_{i}...R_{i}] (both inclusive) which are same when read in forward as well as backward direction. (S[L_{i}.....R_{i}] denotes the substring of S from index L_{i} to R_{i})
If the answer of the i  1^{ th } day was A, L_{i} and R_{i} for the i^{ th } day changes according to the following formula:
where K1 and K2 are constants.
She gives Tappu L_{1} and R_{1} for the 1st day.
Tappu being a little slow in calculations asks for your help.
Would you help him impress his valentine?
.
Input
First line contains the length of string N and the next line contains the string S.
The subsequent line contains the number of queries Q, L_{1}, R_{1}, K1 and K2 respectively.
The indexing of L_{i} and R_{i} is 1based.
Output
Output Q lines each containing the answer for the i^{ th} day.
Constraints
Example
Input: 5 ababc 2 1 3 7 12 Output: 4 5
Explanation
L1 = 1 and R1 = 3
so here the substring is "aba" and the 4 palindromes are "a", "b", "a", "aba".
Using A = 4,
we get L2 = (4 * 1 + 10) % 5 + 1 = 5
and R2 = (4 * 3 + 15) % 5 + 1 = 2,
here L > R so after swapping, L2 = 2 and R2 = 5
so here the resulting substring becomes "babc" and the no. of palindromes is 5 which are "b", "a", "b", "c", "bab".
Author:  sadhwaniyash6 
Tags  sadhwaniyash6 
Date Added:  28022016 
Time Limit:  1  2.5 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, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 