题目描述

你知道的，有些题目不用线段树其实写起来更快，如果你一定要用，那就用吧

小可拿到了一个长度为 $n$ 的数组 $a_{1},a_{2},...,a_{n}$，小达希望小可在 $a$ 上维护一些操作，具体地：

• 操作一：给出下标 $x$（$1 \leq x \leq n$），表示将第 $x$ 个前缀（即 $a_{1},a_{2},...,a_{x}$）全部变为它们的最小值，即：$\min(a_{1},a_{2},...,a_{x})$。

• 操作二：给出下标 $y$（$1 \leq y \leq n$），表示将第 $y$ 个后缀（即 $a_{y},a_{y+1},...,a_{n}$）全部变为它们的最小值，即：$\min(a_{y},a_{y+1},...,a_{n})$。

• 操作三：查询目前 $a$ 中所有元素的和。

你的任务就是帮小可维护这些操作，并回答所有的操作三。

输入格式

第一行两个以空格隔开的整数 $n$ 和 $q$ ，表示数组的大小和操作次数。

第二行输入 n 个以空格隔开的整数，表示 $a_i$。

此后 $q$ 行，第 $i$ 行先输入一个整数 $o_{i}$（$1 \leq o_{i} \leq 3$），表示第 $i$ 次操作的类型，编号同题干。随后在同一行：

• 若 $o_{i} = 1$，输入一个整数 $x_{i}$（$1 \leq x_{i} \leq n$），表示操作的参数。
• 若 $o_{i} = 2$，输入一个整数 $y_{i}$（$1 \leq y_{i} \leq n$），表示操作的参数。

输出格式

对于每次操作类型二，输出一行一个整数表示答案。

样例

8 4
6 2 4 1 5 3 4 6
1 2
3
2 6
3

27
23

样例解释

在这个样例中：

• 进行第一次操作后，$a = \{ 2, 2, 4, 1, 5, 3, 4, 6 \}$，因此总和为：$27$。
• 进行第二次操作后，$a = \{ 2, 2, 4, 1, 5, 3, 3, 3 \}$，因此总和为：$23$。

数据范围

前 $30$ 分，保证 $1 \le n,q \le 10^3$

$100$ 分，保证 $1 \le n,q \le 3*10^5 , 1 \le a_i \le 10^9 , 1 \le x_i,y_i \le n$，保证至少有一个操作类型 $3$ 。