宝藏序列

题目背景

在一个神秘的地下宝库中，存在着一系列由魔法宝石排列而成的序列。每颗宝石都蕴含着特定的魔力值，这些魔力值构成了一个神秘的序列。随着时间的推移和魔法的影响，序列中的魔力值会发生变化，同时，宝库的守护者们也需要不断查询关于这个序列的一些神秘信息。

题目描述

魔力值的累积规则

• 初级魔力累积：对于由 $n$ 颗宝石构成的序列，其魔力值依次为 $a_1, a_2, \cdots, a_n$。从第一颗宝石开始，到第 $i$ 颗宝石的累积魔力值 $S_i$ 定义为这 $i$ 颗宝石魔力值的总和，即 $S_i = \sum_{k = 1}^{i} a_k$。
• 中级魔力累积：将初级累积魔力值 $S_i$ 看作一个新的序列，再次进行累积。从第一个初级累积魔力值开始，到第 $i$ 个初级累积魔力值的累积结果记为 $SS_i$，我们称之为中级累积魔力值。通过数学推导，$SS_i$ 可以用原序列 $S_i$ 表示为 $SS_i=\sum_{j = 1}^{i}S_j$。

守护者的操作指令

宝库的守护者们拥有两种神秘的操作能力，能够对宝石序列进行调整和查询：

1. 魔力修改操作（1 i x）：守护者可以使用魔法将第 $i$ 颗宝石的魔力值修改为 $x$。一旦进行了这样的修改，整个序列的初级和中级累积魔力值都会随之发生变化。
2. 魔力查询操作（2 i）：守护者需要查询第 $i$ 个中级累积魔力值 $SS_i$ 的具体数值，以此来了解宝石序列在特定位置的神秘魔力状况。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示宝石序列的长度以及守护者的操作次数。 第二行有 $N$ 个整数，依次为宝石序列初始的魔力值 $a_1,a_2,\cdots,a_n$。 接下来的 $M$ 行，每行代表守护者的一个操作，操作格式严格按照上述描述。

输出格式

对于每一次魔力查询操作（2 i），输出一行，包含一个整数，即所查询的第 $i$ 个中级累积魔力值 $SS_i$ 的具体数值。

输入输出样例 #1

输入 #1

5 3
1 2 3 4 5
2 5
1 3 2
2 5

输出 #1

35
32

说明/提示

数据范围

• 对于 $30\%$ 的数据：$N\le100$，$M\le100$；
• 对于 $70\%$ 的数据：$N\le 10000$，$M\le10000$；
• 对于 $100\%$ 的数据：$1 \leq N, M\le 200000$， $0\leq a_i\leq 10^3$。

累积魔力值计算示例

• 初始状态：宝石序列的魔力值为 $[1, 2, 3, 4, 5]$。
  • 初级累积魔力值 $S$ 依次为：$S_1 = 1$，$S_2 = 1 + 2 = 3$，$S_3 = 1 + 2 + 3 = 6$，$S_4 = 1 + 2 + 3 + 4 = 10$，$S_5 = 1 + 2 + 3 + 4 + 5 = 15$，即 $S = [1, 3, 6, 10, 15]$。
  • 中级累积魔力值 $SS$ 按照公式 $SS_i=\sum_{j = 1}^{i}\sum_{k = 1}^{j}a_k$ 计算：
    • $SS_1=\sum_{j = 1}^{1}\sum_{k = 1}^{j}a_k=\sum_{k = 1}^{1}a_k=a_1 = 1$；
    • $SS_2=\sum_{j = 1}^{2}\sum_{k = 1}^{j}a_k=\sum_{k = 1}^{1}a_k+\sum_{k = 1}^{2}a_k=a_1+(a_1 + a_2)=1+(1 + 2)=4$；
    • $SS_3=\sum_{j = 1}^{3}\sum_{k = 1}^{j}a_k=\sum_{k = 1}^{1}a_k+\sum_{k = 1}^{2}a_k+\sum_{k = 1}^{3}a_k=a_1+(a_1 + a_2)+(a_1 + a_2 + a_3)=1 + 3+6 = 10$；
    • $SS_4=\sum_{j = 1}^{4}\sum_{k = 1}^{j}a_k=\sum_{k = 1}^{1}a_k+\sum_{k = 1}^{2}a_k+\sum_{k = 1}^{3}a_k+\sum_{k = 1}^{4}a_k=1 + 3+6 + 10 = 20$；
    • $SS_5=\sum_{j = 1}^{5}\sum_{k = 1}^{j}a_k=\sum_{k = 1}^{1}a_k+\sum_{k = 1}^{2}a_k+\sum_{k = 1}^{3}a_k+\sum_{k = 1}^{4}a_k+\sum_{k = 1}^{5}a_k=1 + 3+6 + 10+15 = 35$。即 $SS = [1, 4, 10, 20, 35]$。所以第一次查询 2 5 的结果为 $35$。
• 魔力修改后：当执行 1 3 2 操作后，宝石序列变为 $[1, 2, 2, 4, 5]$。
  • 新的初级累积魔力值 $S$ 依次为：$S_1 = 1$，$S_2 = 1 + 2 = 3$，$S_3 = 1 + 2 + 2 = 5$，$S_4 = 1 + 2 + 2 + 4 = 9$，$S_5 = 1 + 2 + 2 + 4 + 5 = 14$，即 $S = [1, 3, 5, 9, 14]$。
  • 新的中级累积魔力值 $SS$ 按照公式 $SS_i=\sum_{j = 1}^{i}\sum_{k = 1}^{j}a_k$ 计算：
    • $SS_1=\sum_{j = 1}^{1}\sum_{k = 1}^{j}a_k=a_1 = 1$；
    • $SS_2=\sum_{j = 1}^{2}\sum_{k = 1}^{j}a_k=a_1+(a_1 + a_2)=1+(1 + 2)=4$；
    • $SS_3=\sum_{j = 1}^{3}\sum_{k = 1}^{j}a_k=a_1+(a_1 + a_2)+(a_1 + a_2 + a_3)=1 + 3+5 = 9$；
    • $SS_4=\sum_{j = 1}^{4}\sum_{k = 1}^{j}a_k=a_1+(a_1 + a_2)+(a_1 + a_2 + a_3)+(a_1 + a_2 + a_3 + a_4)=1 + 3+5 + 9 = 18$；
    • $SS_5=\sum_{j = 1}^{5}\sum_{k = 1}^{j}a_k=a_1+(a_1 + a_2)+(a_1 + a_2 + a_3)+(a_1 + a_2 + a_3 + a_4)+(a_1 + a_2 + a_3 + a_4 + a_5)=1 + 3+5 + 9+14 = 32$。即 $SS = [1, 4, 9, 18, 32]$。所以第二次查询 2 5 的结果为 $32$。