Cho dãy ~a_1,a_2,...,a_n~ gồm ~n~ số nguyên. Có ~q~ truy vấn, mỗi truy vấn thuộc một trong ~6~ dạng:

• 1 x y z: Với mỗi ~i~ ~(x \le i \le y)~: cập nhật ~a_i=\min(a_i, z)~
• 2 x y z: Với mỗi ~i~ ~(x \le i \le y)~: cập nhật ~a_i=\max(a_i, z)~
• 3 x y z: Với mỗi ~i~ ~(x \le i \le y)~: cập nhật ~a_i= a_i + z~
• 4 l r: Tính ~ \displaystyle \min_{l \le i \le r}a_i~
• 5 l r: Tính ~ \displaystyle \max_{l \le i \le r}a_i~
• 6 l r: Tính ~ \displaystyle \sum_{i=l}^{r}a_i~

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ ~(1 \le n,q \le 10^6)~.
• Dòng thứ hai chứa ~n~ phần tử ~a_i~ ~(|a_i| \le 10^6)~.
• ~q~ dòng tiếp theo, mỗi dòng chứa một truy vấn thuộc một trong ~6~ dạng trên.
• Dữ liệu đảm bảo:
  • ~1 \le x \le y \le n,|z| \le 10^6~ với mỗi truy vấn loại ~1,2,3~;
  • ~1 \le l \le r \le n~ với mỗi truy vấn loại ~4,5,6~.

Output

• Với mỗi truy vấn loại ~4,5,6~, in ra trên một dòng kết quả của truy vấn đó.

Samples

Sample Input 1

5 7
1 2 3 4 5
4 1 5
3 3 4 100
6 1 3
1 2 3 10
5 3 5
2 3 5 20
6 1 5

Sample Output 1

1
106
104
147

Sample Input 2

5 3
5 4 3 2 1
6 1 5
3 3 4 100
6 1 5

Sample Output 2

15
215

Sample Input 3

5 5
1 1 1 1 1
6 1 5
3 3 4 100
4 1 3
3 2 5 99
5 3 5

Sample Output 3

5
1
200

Scoring

• Subtask ~1~ ~(10~ điểm~)~: ~n,q \le 5000~
• Subtask ~2~ ~(10~ điểm~)~: Chỉ có truy vấn loại ~6~
• Subtask ~3~ ~(14~ điểm~)~: Chỉ có truy vấn loại ~4,5,6~
• Subtask ~4~ ~(11~ điểm~)~: Không có truy vấn loại ~1,2,4,5~; ~x=y~ với mọi truy vấn loại ~3~
• Subtask ~5~ ~(12~ điểm~)~: Chỉ có truy vấn loại ~3,6~
• Subtask ~6~ ~(13~ điểm~)~: Không có truy vấn loại ~1,2~
• Subtask ~7~ ~(12~ điểm~)~: ~x=y~ với mọi truy vấn loại ~1,2~
• Subtask ~8~ ~(18~ điểm~)~: Không còn ràng buộc gì thêm