Background

热辣滚烫（2024年贾玲执导的电影）

Description

提示：我们在题目描述的最后提供了一份简要的、形式化描述的题面。

在看完热辣滚烫这部电影后，小 $\omega$ 准备去吃麻辣烫。

一份麻辣烫仅由由若干个配料构成：其中配料美味度 $\alpha$，他的美味度为 $\sum \alpha$，也就是说所有配料美味度的和。

$l\sim r$ 中的所有麻辣烫配料都是小 $\omega$ 喜欢的。

小 $\omega$ 想尝试对于 $l\sim r$ 中的配料的美味度为加在一起。

小 $\omega$ 的仇人小 $\aleph$ 并不知道 $l,r$ 的具体值，但是他知道 $A\le l\le r\le B$，但 $A,B$ 并不是确定的（小 $\omega$ 的口味会改变），而配料美味度也不是一直确定的，所以他要问你 $q$ 个问题。

• 第一种问题，形如 1 x y，表示因为酱料搭配问题，第 $x$ 种配料的美味度变为 $a_y$。
• 第二种问题，形如 2 A B，请你告诉他对于每个 $A\le l\le r\le B$，求出酱料美味度的和。

简要题意：

给你一个长度为 $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)$$

Input

第一行两个整数分别代表 $n,q$。

第二行 $n$ 个整数，第 $i$ 个数字代表第 $i$ 个配料的美味度。

后面 $q$ 行，每行 $3$ 个整数 $[1,2],A,B$。

Output

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

Samples

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

10
20
30

5 6
1 2 3 4 5
1 2 4
2 2 4
1 4 9
2 2 4
1 3 6
2 2 4

36
51
63

Limitation

对于 $20\%$ 的数据，$1\le n,q \leq 100$

对于 $100\%$ 的数据，$0\le n,q,|a_i| \leq 5000$

本题存在 $\Theta(q \log n)$ 的做法，但这题放过了 $\Theta(nq)$。

加强版