Tý được giao nhiệm vụ quản lý một hệ thống gồm \(N\) hồ chứa nước liên kết với nhau. Hồ chứa thứ \(i\) hiện tại đang có mức nước là \(A_i\). Để đảm bảo an toàn đê điều trước mùa mưa bão, Tý cần thực hiện các yêu cầu điều tiết nước sau:

• 1 l r X: Hạ độ cao mực nước của tất cả các hồ chứa từ chỉ số \(l\) đến chỉ số \(r\) xuống tối đa là \(X\). Nghĩa là nếu hồ chứa nào trong khoảng này có mực nước lớn hơn \(X\), mực nước của nó sẽ được rút bớt xuống đúng bằng \(X\); các hồ có mực nước từ \(X\) trở xuống sẽ được giữ nguyên.
• 2 l r: Tính tổng lượng nước hiện có của tất cả các hồ chứa từ chỉ số \(l\) đến chỉ số \(r\).

Hãy viết chương trình hỗ trợ Tý điều tiết hồ chứa nước hiệu quả nhất.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(Q\) (\(1 \le N, Q \le 5 \cdot 10^4\)).
• Dòng hai chứa \(N\) số nguyên đại diện cho mực nước ban đầu của các hồ (\(0 \le a_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa một truy vấn theo định dạng trên.

Định dạng đầu ra

• Với mỗi truy vấn loại 2, in ra tổng lượng nước tìm được.

Ví dụ

Input:

5 3
10 20 30 40 50
1 2 4 25
2 1 5

Output:

130