Gorgeous Sequence

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

There is a sequence a of length n. We use ai 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 xiy, we use min(ai,t) to replace the original ai\'s value.
1 x y: Print the maximum value of ai that xiy.
2 x y: Print the sum of ai that xiy.

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 a1,,an (1in,0ai<231).

Each of the following m lines represents one operation (1xyn,0t<231).

It is guaranteed that T=100n1000000, m1000000.

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
12

Hint

 

Source

2015 Multi-University Training Contest 2