GSS8 - Can you answer these queries VIII


You are given sequence A[0], A[1]...A[N - 1]. (0 <= A[i] < 2^32)

You are to perform Q operations:

  1. 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)
  2. D pos, delete element with index pos from sequence.
  3. R pos val, replace element with idex pos by val. (0 <= val < 2^32)
  4. 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.

Example

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

Output:
6
26
40
4

hide comments
DK...: 2019-11-25 04:49:09

I got Ac in O(k^2*log(n)) per query and using scanf. Nice problem!

mahdibuet3: 2019-11-13 13:15:42

treap does its duty❤

longxiaokong: 2019-10-22 04:10:28

what is the range of N?

[Rampage] Blue.Mary: 2016-02-19 04:34:54

@chalarangleo: O(n) per query will surely lead to TLE. This problem requires O(logn) per query with (a little bit small constant).

Scape: 2015-10-05 16:14:48

A very nice problem!

chalarangelo: 2015-07-19 21:20:37

I'm getting TLE after 27 cases... It works just fine though for any case I can try (even big input), any comments from OP would be appreciated!

Source code here: <snip>

Last edit: 2022-06-27 12:35:51

Added by:Evgeny Savinov
Date:2014-04-14
Time limit:1.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem