Cho mảng gồm \(N\) phần tử là các số nguyên. Nhiệm vụ của bạn là xử lý các loại truy vấn sau:

• \(1\) \(a\) \(b\) \(x\) : Tăng các phần tử từ \(a\) đến \(b\) lên \(x\).
• \(2\) \(a\) \(b\) \(x\) : Thay đổi tất cả các phần tử từ \(a\) đến \(b\) thành \(x\).
• \(3\) \(a\) \(b\) : Tính tổng các phần tử từ \(a\) đến \(b\).

Input

• Dòng thứ nhất gồm hai số nguyên \(N, Q\) là kích thước mảng và số truy vấn.
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) \((1 \leq A_i \leq 10^6)\).
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn thuộc một trong ba 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

• In ra kết quả cho các truy vấn \(3\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N, Q \leq 2.10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(N, Q \leq 2.10^5\).

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