Fun with AGp

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
You are given an 1based array A and its fixed parameters: R, p_{1}, p_{2}. You need to mantain this array, performing some operations. The operations are as follows:
Add an AGP with the start term of S, the common difference of D, common ratio of R from the Xth to the to Yth element of A.
In other words: add S , (S+D)*R , (S+2D)*R^{2} ,....., (S+(YX)*D)*R^{YX} respectively to A[X], A[X+1], ..., A[Y].
Replace the value of A[X] to (A[X])^{g} modulo p_{2}.
In other words: A[x] = (A[X])^{g} modulo p_{2}.
Report the sum of elements in A from the Xth to the Yth modulo p_{1}.
In other words: output (A[X] + ...... + A[Y]) modulo p_{1}.
Input
The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows.The first line of each test case contains 5 single space separated integers: N, Q, R, p_{1}, p_{2}).
The next line contains N single space separated integers (each is between 0 and 100000 inclusive).
Then, there are Q lines denoting the queries in the format, described above.
Output
For each query of the type 2 output the sum of all elements of A from the Xth to the Yth modulo p_{1}.Constraints
 1 ≤ Sum of N over all testcases ≤ 10^{5}
 1 ≤ Sum of Q over all testcases ≤ 10^{5}
 1 ≤ N, Q, S, D ≤ 10^{5}
 p_{1}, p_{2} are primes
 2 ≤ p_{1}, p_{2} ≤ 10^{8}
 1 ≤ R ≤ 10^{9}
 1 ≤ g ≤ 10^{3}
Example
Input2
5 3 2 7 11
0 0 0 0 0
0 2 3 1 3
1 2 2
2 1 5
5 3 3 11 7
1 2 3 4 5
0 2 3 1 3
1 2 2
2 1 5
Output
0
1
Explanation
Initially A = [0,0,0,0,0]
After the first query : A = [2,10,32,0,0]
After the second query : A = [2,1,32,0,0] as (10 * 10) modulo 11 = 1
So in the third query : 2 + 1 + 32 + 0 + 0 = 35 , so 35 modulo 7 = 0
Initially A = [1,2,3,4,5]
After the first query : A = [3,17,75,4,5]
After the second query : A = [3,2,75,4,5] as (17*17) modulo 7 = 2
So in the third query : 3 + 2 + 75 + 4 + 5 = 89 , so 89 modulo 11 = 1
Author:  devuy11 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/FUNAGP 
Tags  bit, devuy11, hard, may14, segmenttree 
Date Added:  8032014 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, CS2, PAS fpc, PAS gpc, GO, NODEJS, HASK, D, FORT, ADA, CAML, ICK, BF, ASM, CLPS, ICON, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, JS, ERL, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions