题目描述

已知一个序列 $a$ 和一个初值为 $0$ 的序列 $b$，你需要进行下面三种操作：

• 1 x y：将 $a_x$ 修改为 $y$。
• 2 l r：对于所有的 $i \in [l, r]$，将 $b_i$ 加上 $\max_{j=l}^{i} a_j$。
• 3 l r：求 $\sum_{i=l}^{r} b_i$。

输入格式

第一行包含两个正整数 $n, m$，分别表示序列 $a$ 的长度和操作次数。

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$，表示序列 $a$。

接下来 $m$ 行，每行行首有一个整数 $op$，表示操作类型，接下来两个整数表示操作参数。

输出格式

对于 $op = 3$ 的操作，输出一行包含一个整数，表示这个询问的答案。

样例输入 1

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

样例输出 1

8
6

样例输入 2

10 10
5 6 10 3 6 7 10 10 1 10 
2 2 4
1 10 7
3 2 8
2 4 5
1 8 2
3 2 2
2 8 9
2 1 2
1 2 10
3 2 3

样例输出 2

26
6
22

数据范围

对于 $100\%$ 的数据，保证 $1 \le n, m \le 5 \times 10^5$， $1 \le l \le r \le n$，$1 \le x \le n$，$1 \le a_i, y \le 10^9$。