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 \times 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\), \(2\) \(a\) \(b\) \(x\), hoặc \(3\) \(a\) \(b\) \((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