Problem - 5306: Gorgeous Sequence

Problem Description

There is a sequence $a$ of length $n$. We use $a_i$ to denote the $i$-th element in this sequence. You should do the following three types of operations to this sequence:

• $0\ x\ y\ t$: For every $x \le i \le y$, we use $\min(a_i, t)$ to replace the original $a_i$'s value.
• $1\ x\ y$: Print the maximum value of $a_i$ that $x \le i \le y$.
• $2\ x\ y$: Print the sum of $a_i$ that $x \le i \le y$.

Input

The first line of the input is a single integer $T$, indicating the number of testcases.
The first line contains two integers $n$ and $m$ denoting the length of the sequence and the number of operations.
The second line contains $n$ separated integers $a_1, \ldots, a_n$ ($\forall 1 \le i \le n, 0 \le a_i < 2^{31}$).
Each of the following $m$ lines represents one operation ($1 \le x \le y \le n, 0 \le t < 2^{31}$).
It is guaranteed that $T=100$, $\sum n \le 1000000$, $\sum m \le 1000000$.

Output

For every operation of type 1 or 2, print one line containing the answer to the corresponding query.

Sample Input

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

Sample Output

5
15
3
9

Hint

Please use efficient IO method.

Author

XJZX

Source

HDU Online Judge