E-小苯的数组操作_牛客周赛 Round 125

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小苯拿到了一个长度为 $n$ 的数组 $a_1,a_2,\dots,a_n$ ，小红希望小苯在 $a$ 上维护一些操作，具体地：
$\hspace{23pt}\bullet\,$ 操作一：给出下标 $x\left(1 \leqq x \leqq n\right)$ ，表示将第 $x$ 个前缀（即 $a_1,a_2,\dots,a_x$ ）全部变为他们的最小值，即： $\min(a_1,a_2,\dots,a_x)$ 。
$\hspace{23pt}\bullet\,$ 操作二：给出下标 $y\left(1 \leqq y \leqq n\right)$ ，表示将第 $y$ 个后缀（即 $a_y,a_{y+1},\dots,a_n$ ）全部变为他们的最小值，即： $\min(a_y,a_{y+1},\dots,a_n)$ 。
$\hspace{23pt}\bullet\,$ 操作三：查询目前 $a$ 中所有元素的和。
$\hspace{15pt}$ 你的任务就是帮小苯维护这些操作，并回答所有的操作三。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入两个正整数 ，分别表示数组的长度、操作的次数。
第二行输入  个整数 ，表示数组中的各个元素。
此后  行，第  行先输入一个整数 ，表示第  次操作的类型，编号同题干。随后在同一行：
若 ，输入一个整数 ，表示操作的参数。
若 ，输入一个整数 ，表示操作的参数。

除此之外，保证单个测试文件的  之和、 之和均不超过 ，且至少存在一次操作三。

输出描述:

对于每一次操作三，新起一行输出一个整数，表示当前数组中所有元素的和。

示例1

输入

复制

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

输出

复制

27
23

说明

在这个样例中：
进行第一次操作后，，因此总和为：。
进行第二次操作后，，因此总和为：。