Dãy tuyệt đẹp (Gorgeous Sequence)

Nguồn: HDU

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho dãy $a_1,\ldots,a_n$ và thực hiện $m$ thao tác:

• 0 l r t: với mọi $i\in[l,r]$, gán $a_i\leftarrow\min(a_i,t)$.
• 1 l r: in giá trị lớn nhất trên $[l,r]$.
• 2 l r: in tổng trên $[l,r]$.

Input

Dòng đầu chứa $n,m$. Dòng thứ hai chứa $n$ phần tử. Mỗi trong $m$ dòng sau là 0 l r t, 1 l r hoặc 2 l r.

Output

Với thao tác loại 1 in cực đại; với thao tác loại 2 in tổng, mỗi kết quả trên một dòng.

Subtask

• Subtask 1 (20%): n,m≤30; các điều kiện khác giữ như bài đầy đủ.

• Subtask 2 (30%): n,m≤3000; các điều kiện khác giữ như bài đầy đủ.

• Subtask 3 (50%): toàn bộ giới hạn:

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

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

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

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

Ví dụ

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

Giải thích

Với [1,2,3,4,5], 0 3 5 3 chỉ hạ 4 và 5 xuống 3, dãy thành [1,2,3,3,3]; max là 3 và sum là 12.