7408: GSS8 - Can you answer these queries VIII
[Creator : ]
Description
You are given sequence A[0], A[1]...A[N - 1]. (0 <= A[i] < 2^32)
You are to perform Q operations:
- I pos val, insert number val in sequence before element with index pos. (0 <= val < 2^32, if pos = current_length then you should add number to the end of the sequence)
- D pos, delete element with index pos from sequence.
- R pos val, replace element with idex pos by val. (0 <= val < 2^32)
- Q l r k, answer Σ A[i] * (i - l + 1)^k modulo 2^32, for l <= i <= r. (0 <= k <= 10)
Input
The first line of the input contains an integer N (1 <= N <= 100000).
The following line contains N integers, representing the starting sequence A[0]...A[N-1].
The third line contains an integer Q (0 <= Q <= 100000).
Next Q lines contains the queries in given format.
Output
For each "Q" operation, print an integer (one per line) as described above.
Sample 1 Input
4
1 2 3 5
7
Q 0 2 0
I 3 4
Q 2 4 1
D 0
Q 0 3 1
R 1 2
Q 0 1 0
Sample 1 Output
6
26
40
4