Cho một dãy số nguyên có ~N~ phần tử ~A_{1}, A_{2}, A_{3}, ..., A_{N}~ và ~Q~ truy vấn. Mỗi truy vấn có 1 trong hai dạng:

• Dạng ~1~: ~1\ l\ r\ x~ : tăng tất cả các giá trị từ ~l~ đến ~r~ lên ~x~ đơn vị.
• Dạng ~2~: ~2\ l\ r~ : tính tổng tất cả các phần tử trong đoạn từ ~l~ đến ~r~.

Input

• Dòng đầu chứa hai số nguyên ~N~ và ~Q~
• Dòng thứ hai chứa ~N~ số nguyên ~A_{1}, A_{2}, A_{3}, ..., A_{N}~
• ~Q~ dòng tiếp theo mỗi dòng là các truy vấn dạng ~1~ hoặc dạng ~2~

Biết rằng

• ~1 \leq N, Q \leq 10^5; 1 \leq A_{i} \leq 10^5; 1 \leq l \leq r \leq N; 1 \leq x \leq 10^5~

Output

• In ra kết quả của các truy vấn dạng ~2~. Mỗi kết quả này được ghi trên 1 dòng

Sample

Input #1

6 7
1 2 3 4 5 6
1 1 6 3
2 1 6
1 2 4 2
1 5 6 2
1 1 3 4
1 3 5 2
2 3 6

Output #1

39
48