题目描述

有 $n$ 位同学完成了考试，学号从 $1\sim n$。33DAI 登记了他们的成绩 $a_1\sim a_n$。

他总是容易登记错，但还行，他最多只会错 $3$ 次。老师会经常问他某段学号连续的同学 $l\sim r$ 的成绩之和，也会经常提示他某位同学的成绩错了。

请你帮 33DAI 回答老师的每次问题。

具体来说，你先会得到 $n$ 位同学初始登记的成绩，然后有 $q$ 次操作，每次操作的格式如下：

• $1$ 号操作会告诉你 1 l r：表示查询当前 $a_l\sim a_r$ 这些数之和。
• $2$ 号操作会告诉你 2 x y：表示把 $a_x$ 的值改为 $y$。

输入格式

第一行两个数 $n,q$。

第二行 $n$ 个数 $a_1\sim a_n$。

接下来 $q$ 行，每次是一次操作的三个数 1 l r 或 2 x y。

输出格式

对于每次 $1$ 号操作，输出 $a_l\sim a_r$ 这些数之和。

5 6
1 1 1 1 1 
1 2 4
2 3 3
1 2 4
2 1 7
1 2 4
1 1 5

3
5
5
13

样例 1 解释

• 初始成绩为 1 1 1 1 1
• 1 2 4：查询 $a_2\sim a_4$ 之和，为 $3$
• 2 3 3：把 $a_3$ 修改为 $3$，成绩变为 1 1 3 1 1
• 1 2 4：查询 $a_2\sim a_4$ 之和，为 $5$
• 2 1 7：把 $a_1$ 修改为 $7$，成绩变为 7 1 3 1 1
• 1 2 4：查询 $a_2\sim a_4$ 之和，为 $5$
• 1 1 5：查询 $a_1\sim a_5$ 之和，为 $13$

数据规模与约定

对于 $100\%$ 的数据，$1 \le n,q \le 10^5$，$1\le l\le r\le n$，$1\le x\le n$，$1\le a_i,y\le 10^9$。33DAI 最多只会登记错误 $3$ 次成绩，所以 $2$ 号操作次数不超过 $3$

• 子任务 1（30 分）：保证 $n=1$。
• 子任务 2（30 分）：保证没有 $2$ 号操作。
• 子任务 3（40 分）：没有特殊限制。