Nhập vào một mảng chứa \(n\) số nguyên. Cần trả lời \(q\) truy vấn, mỗi truy vấn thuộc một trong ba loại sau:

1. Tăng giá trị của tất cả các phần tử trong đoạn \([l,\ r]\) lên \(v\) đơn vị;
2. Gán giá trị của tất cả các phần tử trong đoạn \([l,\ r]\) bằng v;
3. In ra tổng của tất cả các phần tử trong đoạn \([l,\ r]\).

Input

• Dòng đầu chứa hai số nguyên \(n\) và \(q\): lần lượt là kích thước của mảng và số lượng truy vấn;
• Dòng thứ hai chứa \(n\) số nguyên \(x_1,\ x_2,\ldots,\ x_n\): giá trị của các phần tử trong mảng;
• Cuối cùng là \(q\) dòng mô tả \(q\) truy vấn. Mỗi truy vấn có dạng "\(1\ l\ r\ v\)", "\(2\ l\ r\ v\)", hoặc "\(3\ l\ r\)".

Output

• Với mỗi truy vấn loại \(3\), in ra kết quả trên một dòng.

Ràng buộc

• \(1\leq n,\ q\leq2\times10^5\);
• \(1\leq x_i,\ v\leq10^9\);
• \(1\leq p\leq n\);
• \(1\leq l\leq r\leq n\).

Ví dụ

Sample input

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

Sample output

7
11
15