U396440 Dawn

> 黎明，是一首诗，一幅画，一曲动人的音乐。黑夜渐渐退去，黎明悄然降临，带给大地无尽的希望与活力。

给你一个长度为 $n$ 的序列 $a$。 定义 $\text{Sum}(i,j)$ 表示 $(a_{i}+a_{i+1}+...+a_j)$。 共 $q$ 次操作，每次操作有两种类型： * `1 x y` 把 $a_{x}$ 改为 $y$ * `2 l r` 请你求出下面这个式子： $$ \sum_{i=l}^r \sum_{j=i}^r \text{Sum}(i,j) $$ **保证在当前数据范围的限制下，上式答案在 `long long` 的范围内。**

第一行是两个整数，分别代表 $n,q$。 第二行有 $n$ 个整数，表示序列 $a$。 后面 $q$ 行，每行一个操作。

对于每个操作 $2$，输出你的答案。

对于 $40\%$ 的数据，$n,q \le 2000$。 对于另外 $30\%$ 的数据，没有操作 $1$。 对于所有数据，$n,q \le 2 \times 10^5,a_i \le 1000$。