Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên dương \(A_1,A_2..A_N\). Cho \(Q\) thao tác thực hiện lần lượt, thao tác thứ \(i\) sẽ có một trong hai loại như sau:

• \(1\) \(u_i\) \(v_i\) \(x_i\): Tăng mỗi phần tử từ vị trí \(u_i\) tới vị trí \(v_i\) lên \(x_i\) đơn vị
• \(2\) \(u_i\) \(v_i\): Tính tổng các phần tử từ vị trí \(u_i\) tới vị trí \(v_i\).

Yêu cầu

Thực hiện tất cả \(Q\) thao tác và in ra kết quả của thao tác loại \(2\).

Dữ liệu vào

• Dòng thứ nhất gồm hai số nguyên dương \(N,Q\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ... A_N\) \((A_i \le 10^9)\)
• \(Q\) dòng tiếp theo, với dòng thứ \(i\): số đầu tiên trên dòng là \(1\) hoặc \(2\). Số \(1\) theo sau bởi ba số nguyên dương \(u_i\) \(v_i\) và \(x_i\) \((1 \le u_i \le v_i \le N, 1 \le x_i \le 10^9)\). Số \(2\) theo sau bởi hai số nguyên dương \(u_i\) và \(v_i\) \((1 \le u_i \le v_i \le N)\)

Dữ liệu ra

• Với thao tác loại \(2\) có dạng \(2 u v\), in ra tổng các phần tử từ vị trí \(u\) tới vị trí \(v\) trên một dòng.

Ràng buộc

• Subtask 1 (30% số điểm): \(N \le 10^3, Q \le 10^3\)
• Subtask 2 (30% số điểm): mọi thao tác loại 1 có \(u=v\)
• Subtask 3 (40% số điểm): Không có ràng buộc gì thêm

Input 1

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

Output 1

13
30