题目描述

有若干个小球放在数轴上，第 $i$ 号小球的坐标参数为 $a_i$。

有两种操作：

1. 输入 $i,v$，修改第 $i$ 号小球的坐标参数为 $a_i\gets v$；

2. 输入 $l,r$，询问下述内容：

   按照 $a_i$ 从小到大的顺序（$a_i$ 相等时按 $i$ 从小到大的顺序）依次将小球放在数轴上。第 $i$ 号小球放在 $\le a_i$ 的没有被之前放置的小球占据的最大的整点处，设第 $i$ 号小球放置的位置为 $b_i$。

   请你输出 $\sum_{i=1,2,\dots , n,[l,r]\subseteq [b_i,a_i]} (a_i+b_i)$ 的值。也即，所有满足 $b_i\le l,a_i\ge r$ 的小球的 $a_i+b_i$ 之和。

输入格式

从标准输入读入数据。

第一行两个正整数 $n,q$，分别表示小球个数和操作次数。

第二行 $n$ 个整数 $a_1, a_2, \dots , a_n$，用空格分隔，表示初始的坐标参数。

接下来 $q$ 行每行是下列两种之一：

1. $\mathtt{1\ i\ v}$ 表示修改第 $i$ 个小球的坐标参数为 $a_i\gets v$；

2. $\mathtt{2\ l\ r}$ 表示询问 $\sum_{i=1,2,\dots , n,[l,r]\subseteq [b_i,a_i]} (a_i+b_i)$。

输出格式

输出到标准输出。

对于每种操作 $\mathtt{2}$，输出一行一个整数表示答案。

样例 1

input

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

output

17
8
18
0

最开始，三个小球的位置依次为：

1. $b_1=5, a_1=5$；
2. $b_2=4, a_2=5$；
3. $b_3=3, a_3=5$。

修改之后，三个小球的位置依次为：

1. $b_2=4, a_2=4$；
2. $b_1=5, a_1=5$；
3. $b_3=3, a_3=5$。

样例 2

input

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

output

20
10
0
0
20
12
9

见附加文件（点击页面上方「附加文件」按钮下载）。

数据范围与提示

对于所有数据，$1\le n \le 10^5 ,1\le q\le 2\times 10^5 , n< a_i,v \le 2n , 1\le l \le r \le 2n$。

详细的数据限制及约定如下（留空表示和上述所有数据的约定相同）：