Truy vấn trên mảng

Cho một mảng gồm \(N\) phần tử nguyên. Nhiệm vụ của bạn là thực hiện các truy vấn thuộc một trong ba loại sau:

• 1 a b x --- Cộng thêm \(x\) vào tất cả các phần tử trong đoạn \([a, b]\).
• 2 a b x --- Gán tất cả các phần tử trong đoạn \([a, b]\) bằng \(x\).
• 3 a b --- In ra tổng các phần tử trong đoạn \([a, b]\).

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\) \((1 \leq N, Q \leq 2 \cdot 10^5)\) --- số phần tử của mảng và số truy vấn.
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, \ldots, A_N\) \((1 \leq A_i \leq 10^6)\) --- các phần tử ban đầu của mảng.

• \(Q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn theo một trong ba định dạng sau:

• 1 a b x \((1 \leq a \leq b \leq N, 1 \leq x \leq 10^6)\).

• 2 a b x \((1 \leq a \leq b \leq N, 1 \leq x \leq 10^6)\).
• 3 a b \((1 \leq a \leq b \leq N)\).

Output

Với mỗi truy vấn loại 3, in ra một dòng chứa tổng các phần tử trong đoạn \([a, b]\) tại thời điểm đó.

Example

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

7
11
15

Scoring

• Subtask 1 (25% số điểm): \(N, Q \leq 2000\).
• Subtask 2 (25% số điểm): Không có truy vấn loại \(2\).
• Subtask 3 (25% số điểm): Không có truy vấn loại \(1\).
• Subtask 4 (25% số điểm): Không có ràng buộc gì thêm.