Gorgeous Sequence

Source: HDU

Version: Phuoc Hung OJ Extended

Problem Statement

Given $a_1,\ldots,a_n$, process $m$ operations:

• 0 l r t: for every $i\in[l,r]$, set $a_i\leftarrow\min(a_i,t)$.
• 1 l r: print the maximum on $[l,r]$.
• 2 l r: print the sum on $[l,r]$.

Input

The first line contains $n,m$. The second line contains the array. Each of the next $m$ lines is 0 l r t, 1 l r, or 2 l r.

Output

For type 1 print the range maximum; for type 2 print the range sum, one answer per line.

Subtasks

• Subtask 1 (20%): n,m≤30; all other conditions are unchanged.

• Subtask 2 (30%): n,m≤3000; all other conditions are unchanged.

• Subtask 3 (50%): full constraints:

• $1\le n,m\le10^6$

• $0\le a_i<2^{31}$

• $0\le t<2^{31}$

• $1\le l\le r\le n$

Examples

Input

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

Output

5
15
3
12

Explanation

Applying chmin 3 to positions 3..5 changes [1,2,3,4,5] into [1,2,3,3,3], whose maximum is 3 and sum is 12.