Gorgeous Sequence

问题描述

有一个长度为 $n$ 的序列 $a$，用 $a_i$ 表示序列中的第 $i$ 个元素。你需要对这个序列执行以下三种操作：

1. $0\ x\ y\ t$：对于所有 $x \le i \le y$，将 $a_i$ 的值替换为 $\min(a_i, t)$。
2. $1\ x\ y$：输出 $x \le i \le y$ 的 $a_i$ 中的最大值。
3. $2\ x\ y$：输出 $x \le i \le y$ 的 $a_i$ 的和。

输入

输入的第一行是一个整数 $T$，表示测试用例的数量。
每个测试用例的第一行包含两个整数 $n$ 和 $m$，分别表示序列的长度和操作的数量。
第二行包含 $n$ 个整数 $a_1, \ldots, a_n$（对于所有 $1 \le i \le n$，满足 $0 \le a_i < 2^{31}$）。
接下来的 $m$ 行每行表示一个操作（满足 $1 \le x \le y \le n$，$0 \le t < 2^{31}$）。
保证 $T=100$，所有测试用例的 $n$ 之和不超过 $1000000$，所有测试用例的 $m$ 之和不超过 $1000000$。

输出

对于每个类型为 1 或 2 的操作，输出一行，包含对应查询的答案。

样例输入

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

样例输出

5
15
3
12

提示

请使用高效的输入输出方法。

作者

XJZX

来源

HDU Online Judge