長さ $N$ の数列 $A_1, A_2, \ldots, A_N$ が与えられる．以下のクエリを処理するプログラムを作成せよ：

• 1 i v: $A_i$ を $v$ に設定する．
• 2 k i j: $k$ 番目のタイプ1のクエリが適用された時点での $A_i, A_{i+1}, \ldots, A_j$ の和を出力する．

入力

1行目に数列の長さ $N$ が与えられる（$1 \le N \le 100{,}000$）．

2行目に $A_1, A_2, \ldots, A_N$ が与えられる（$1 \le A_i \le 1{,}000{,}000$）．

3行目にクエリの個数 $M$ が与えられる（$1 \le M \le 100{,}000$）．

続く $M$ 行に各クエリが与えられる．タイプ1のクエリでは $1 \le i \le N$, $1 \le v \le 1{,}000{,}000$ を満たす．タイプ2のクエリでは $1 \le i \le j \le N$ であり，$k$ は $0 \le k \le$（その時点までに与えられたタイプ1のクエリの個数）を満たす．

入力に含まれる数値はすべて整数である．

出力

タイプ2のクエリごとに，その和を出力せよ．

入出力例

入力 1

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

出力 1

6
9
14
17
15