Kẹp Hai Phía

Cho dãy số nguyên $a_0,\dots ,a_{n-1}$. Mọi đoạn trong bài là đoạn nửa mở $[l,r)$, gồm các chỉ số $l,l+1,\dots ,r-1$. Hỗ trợ:

• $0$ $l$ $r$ $b$: gán $a_i=\min (a_i,b)$ trên đoạn.
• $1$ $l$ $r$ $b$: gán $a_i=\max (a_i,b)$ trên đoạn.
• $2$ $l$ $r$ $b$: cộng $b$ vào mỗi phần tử trên đoạn.
• $3$ $l$ $r$: in tổng các phần tử trên đoạn.

Input

• Dòng đầu chứa $n$ và $q$.
• Dòng thứ hai chứa $n$ phần tử ban đầu.
• $q$ dòng tiếp theo mô tả các thao tác theo một trong bốn dạng trên.

Output

• Với mỗi thao tác loại $3$, in tổng cần tìm trên một dòng.

Constraints

• $1\le n,q\le 2\cdot 10^5$.
• $-10^{12}\le a_i,b\le 10^{12}$.
• $0\le l<r\le n$; mọi giá trị trung gian và tổng vừa số nguyên $64$ bit có dấu.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n,q\le 2000$ và mọi giá trị tuyệt đối không vượt $10^6$ trong suốt quá trình.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

4 7
5 -2 9 4
3 0 4
0 0 3 6
1 1 4 1
2 0 2 -3
3 0 4
0 2 4 3
3 1 4

16
10
4