Nhiệm vụ của bạn là duy trì một mảng gồm \(n\) giá trị và xử lý hiệu quả các truy vấn sau:

1. Tăng mỗi giá trị trong đoạn \([a, b]\) lên \(x\).
2. Gán mỗi giá trị trong đoạn \([a, b]\) thành \(x\).
3. Tính tổng các giá trị 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})\) - kích cỡ của mảng và số lượng truy vấn.
• Dòng tiếp theo chứa \(n\) số nguyên \(t_1, t_2, \ldots, t_n\) \((1 \leq t_i \leq 10^6)\) - các giá trị ban đầu của mảng.
• \(q\) dòng cuối cùng mô tả truy vấn. Định dạng của mỗi dòng là một trong các kiểu sau:
  • \(1\) \(a\) \(b\) \(x\): tăng các phần tử trong đoạn \([a,b]\) lên \(x\)
  • \(2\) \(a\) \(b\) \(x\): gán các phần tử trong đoạn \([a,b]\) thành \(x\)
  • \(3\) \(a\) \(b\): tính tổng đoạn \([a,b]\)
• Với \(1 \leq a \leq b \leq n\), \(1 \leq t_i, x \leq 10^6\)

Output

• In ra kết quả cho từng truy vấn tính tổng.

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