You are given a string S of length N and Q queries.
In the ith query, you are asked about the number of palindromes between Li and Ri (both inclusive).
If the answer of the i-1'th query was A, Li and Ri are generated as follows:
Li = ((A * Li-1 + X) % N) + 1
Ri = ((A * Ri-1 + Y) % N) + 1
where X and Y are constants.
If Li > Ri, then swap values of Li and Ri.
L1 and R1 are given to you for the 1st day.
Input :
First line contains the length of string i.e N and the next line contains the string S.
The next line contains the no. of queries Q, L1, R1, X and Y resp.
(1-based indexing is used).
Output : Q lines each containing the answer for the i'th query.
Constraints :
- 1 <= N, Q <= 5 * 10 ^ 5
- 1 <= L, R <= N
- 0 <= X, Y <= 10 ^ 9
L1 = 1 and R1 = 3
The 4 palindromes are "a","b","a","aba".
Using A=4,
we get L2 = (4x1 + 10) % 5 + 1 = 5
and R2 = (4x3 + 15) % 5 + 1 = 2,
here L2 > R2 so after swapping , L2 = 2 and R2 = 5
The palindromes in the range [2,5] are "b","a","b","c","bab".
