Weighted sum queries on a mutable sequence

You are given a sequence $A_0, A_1, \dots, A_{N-1}$ of length $N$. Every element satisfies $0 \le A_i < 2^{32}$. Process the following four queries in the given order.

• 1 p v: insert $v$ immediately before $A_p$. If $p$ equals the current length of the sequence, append $v$ at the end. ($0 \le p \le$ length of the sequence, $0 \le v < 2^{32}$)
• 2 p: remove $A_p$. ($0 \le p <$ length of the sequence)
• 3 p v: replace $A_p$ with $v$. ($0 \le p <$ length of the sequence, $0 \le v < 2^{32}$)
• 4 l r k: print $\left( \sum_{i=l}^{r} A_i \times (i - l + 1)^k \right) \bmod 2^{32}$. ($0 \le l \le r <$ length of the sequence, $0 \le k \le 10$)

An insertion or a removal shifts the index of every element after it by one. The values $p$, $l$, and $r$ in a query refer to the sequence as it stands when that query is processed.

The weight $(i - l + 1)^k$ in query 4 is the position of $A_i$ inside the range, counted from the left end starting at 1, raised to the power $k$.

The first line contains the size of the sequence $N$ ($1 \le N \le 100000$).

The second line contains $A_0, A_1, \dots, A_{N-1}$, separated by spaces.

The third line contains the number of queries $M$ ($1 \le M \le 100000$).

Each of the next $M$ lines contains one query.

For every query of type 4, print the answer on its own line. Queries of type 1, 2, and 3 print nothing.