A sequence $A_0, A_1, \ldots, A_{N-1}$ of length $N$ is given. Write a program that processes the following queries ($0 \le A_i < 2^{32}$):

• 1 p v: Insert $v$ before $A_p$. If $p$ equals the length of $A$, it is inserted at the end. ($0 \le p \le$ length of $A$, $0 \le v < 2^{32}$)
• 2 p: Remove $A_p$. ($0 \le p <$ length of $A$)
• 3 p v: Change $A_p$ to $v$. ($0 \le p <$ length of $A$, $0 \le v < 2^{32}$)
• 4 l r k: Compute $(\sum A_i \times (i - l + 1)^k) \bmod 2^{32}$ and output it. ($0 \le k \le 10$)

Input

The first line contains the length of the sequence $N$ ($1 \le N \le 100{,}000$).

The second line contains $A_0, A_1, \ldots, A_{N-1}$.

The third line contains the number of queries $M$ ($1 \le M \le 100{,}000$).

The next $M$ lines each contain one query.

Output

For each query, output the answer on a separate line.

Examples

Input 1

4
1 2 3 5
7
4 0 2 0
1 3 4
4 2 4 1
2 0
4 0 3 1
3 1 2
4 0 1 0

Output 1

6
26
40
4