题目描述

给你一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$。接下来有 $m$ 次操作，操作分为如下死四种类型：

• CHANGE p x：将 $a_p$ 的值修改为 $x$；
• MAX l r：查询区间 $[l, r]$ 元素最大值；
• MIN l r：查询区间 $[l, r]$ 元素最小值；
• SUM l r：查询区间 $[l, r]$ 元素和。

请你依次执行每次操作，并对查询操作输出对应的结果。

输入格式

第一行，两个整数 $n$ 和 $m$，表示数列长度及操作次数（$1 \le n,m \le 2 \cdot 10^5$）。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n$，以空格分隔（$1 \le a_i \le 10^9$）。

接下来 $m$ 行，每行包含一次操作（对于 CHANGE p x 操作，保证 $1 \le p \le n, 1 \le x \le 10^9$，对于其它操作，保证 $1 \le l \le r \le n$）。

输出格式

对于每次查询操作，输出一行，包含一个整数，表示对应的结果。

样例

7 6
1 2 3 4 5 6 7
SUM 1 3
MAX 2 5
CHANGE 2 8
SUM 1 3
MAX 2 5
MIN 2 7

6
5
12
8
3