長さ $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$)。

2 行目には $A_0, A_1, \ldots, A_{N-1}$ が含まれる。

3 行目にはクエリの数 $M$ が含まれる ($1 \le M \le 100{,}000$)。

続く $M$ 行にはそれぞれ 1 つのクエリが含まれる。

出力

各クエリに対し、答えを別の行に出力せよ。

入出力例

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