Conan ngày hôm nay không cần phá án, mà phải trả lời một câu đố truy vấn hỗn hợp từ Kid.

Cho mảng số nguyên ~A~ độ dài ~N~ và ~Q~ truy vấn thuộc một trong tám loại sau:

• Truy vấn loại ~1~ có dạng ~1 \; l \; r \; x~: Cập nhật ~A_i=A_i+x~ với mọi ~l \le i \le r~
• Truy vấn loại ~2~ có dạng ~2 \; l \; r \; x~: Cập nhật ~A_i=max(A_i,x)~ với mọi ~l \le i \le r~
• Truy vấn loại ~3~ có dạng ~3 \; l \; r \; x~: Cập nhật ~A_i=min(A_i,x)~ với mọi ~l \le i \le r~
• Truy vấn loại ~4~ có dạng ~4 \; l \; r~: Tính tổng ~A_l+A_{l+1}+...+A_r~
• Truy vấn loại ~5~ có dạng ~5 \; l \; r~: Xác định giá trị ~max\{A_l,A_{l+1},...,A_r\}~
• Truy vấn loại ~6~ có dạng ~6 \; l \; r~: Đếm số lượng chỉ số ~i~ ~(l \le i \le r)~ thỏa mãn ~A_i=max\{A_l,A_{l+1},...,A_r\}~
• Truy vấn loại ~7~ có dạng ~7 \; l \; r~: Xác định giá trị ~min\{A_l,A_{l+1},...,A_r\}~
• Truy vấn loại ~8~ có dạng ~8 \; l \; r~: Đếm số lượng chỉ số ~i~ ~(l \le i \le r)~ thỏa mãn ~A_i=min\{A_l,A_{l+1},...,A_r\}~

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~Q~ ~(1 \le N,Q \le 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên mảng ~A~ ~(-10^6 \le A_i \le 10^6)~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa một trong tám loại truy vấn trên.

Output

• Với mỗi truy vấn loại ~4~, ~5~, ~6~, ~7~ và ~8~, in ra kết quả trên một dòng.

Samples

Sample Input 1

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

Sample Output 1

15
106
104
1
119
2
1
147

Sample Input 2

5 4
2 5 5 2 5
5 1 5
6 1 5
7 1 5
8 1 5

Sample Output 2

5
3
2
2

Scoring

Trong tất cả các truy vấn, ~1 \le l \le r \le N~ và ~-10^6 \le x \le 10^6~.

• Subtask ~1~ với ~7\%~ số điểm: ~N,Q \le 5000~
• Subtask ~2~ với ~10\%~ số điểm: Chỉ có truy vấn loại ~4~
• Subtask ~3~ với ~12\%~ số điểm: Chỉ có truy vấn loại ~1~ và ~4~; ~l=r~ với mọi truy vấn loại ~1~.
• Subtask ~4~ với ~11\%~ số điểm: Chỉ có truy vấn loại ~1~ và ~4~
• Subtask ~5~ với ~19\%~ số điểm: Chỉ có truy vấn loại ~1~, ~4~, ~5~ và ~7~
• Subtask ~6~ với ~19\%~ số điểm: Không có truy vấn loại ~2~ và ~3~.
• Subtask ~7~ với ~13\%~ số điểm: Chỉ có truy vấn loại ~2~ và ~4~.
• Subtask ~8~ với ~9\%~ số điểm: Không có ràng buộc gì thêm