给定一个长度为 $N$ 的序列 $A_0, A_1, \ldots, A_{N-1}$。编写一个程序处理以下查询（$0 \le A_i < 2^{32}$）：

• 1 p v：在 $A_p$ 之前插入 $v$。如果 $p$ 等于 $A$ 的长度，则插入到末尾。（$0 \le p \le$ $A$ 的长度，$0 \le v < 2^{32}$）
• 2 p：删除 $A_p$。（$0 \le p <$ $A$ 的长度）
• 3 p v：将 $A_p$ 修改为 $v$。（$0 \le p <$ $A$ 的长度，$0 \le v < 2^{32}$）
• 4 l r k：计算 $(\sum A_i \times (i - l + 1)^k) \bmod 2^{32}$ 并输出。（$0 \le k \le 10$）

输入格式

第一行包含序列的长度 $N$（$1 \le N \le 100{,}000$）。

第二行包含 $A_0, A_1, \ldots, A_{N-1}$。

第三行包含查询数量 $M$（$1 \le M \le 100{,}000$）。

接下来 $M$ 行每行包含一个查询。

输出格式

对于每个查询，在一行中输出答案。

样例

输入 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

输出 1

6
26
40
4