SegTree - segment tree

長さ $N$ の数列 $A$ があります。以下のクエリを処理してください。

1. $A_p$ を $x$ に変更する。
2. $l \leq i < r$ をみたす $i$ について、 $A_i$ の和を出力する。
   $Q$ 個のクエリが与えられます。

制約

• $N = 1024$
• $0 \leq A_i \leq 1000 \; (1 \leq i \leq N)$
• $1 \leq Q \leq 1000$
  • クエリ 1 について、$1 \leq p \leq N, \; 0 \leq x \leq 1000$
  • クエリ 2 について、$1 \leq l < r \leq N + 1$

入力

$N$

$A_1~A_2~...~A_N$

$Q$

$query_1$

$query_2$

$\vdots$

$query_Q$

各 $query$ は以下のように与えられます。

• 1 の場合：

$1~p~x$

• 2 の場合：

$2~l~r$

出力

クエリ 2 の答えを順番に出力してください。

入出力例

入力例

8
1 2 4 2 5 0 0 0
3
2 1 4
1 2 3
2 1 6
Copy

出力例

7
15
Copy

このケースは $N = 1024$ を満たさないことに注意してください。