Cho mảng \(A\) gồm \(n\) số nguyên. Cho \(q\) truy vấn thuộc một trong hai dạng:

• \(1\) \(l\) \(r\) \(x\): Tăng các phần tử từ \(l\) đến \(r\) lên \(x\)
• \(2\) \(l\) \(r\): Tính tổng các phần tử trong đoạn \(A_l, A_{l+1}... A_r\)

Dữ liệu vào

• Dòng đầu tiên là số \(n, q\) \((1 \le n \le 10^5)\) \((1 \le q \le 10^5)\)
• Dòng thứ hai là \(n\) số nguyên \(A_i\) \((|A_i| \le 10^6)\)
• \(q\) dòng sau, mỗi dòng là một truy vấn thuộc một trong hai loại trên.

Dữ liệu ra

• Với mỗi truy vấn loại 2, hãy in ra câu trả lời trên một dòng.

Input 1

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

Output 1

8
12