给定长度为 $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$ 的和。

输入格式

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

第二行包含 $A_1, A_2, \ldots, A_N$。$(1 \le A_i \le 1{,}000{,}000)$

第三行包含查询的数量 $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$，且 $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