Cho dãy ~a_1, a_2, \dots, a_n~ gồm ~n~ phần tử, bạn cần thực hiện ~q~ truy vấn theo thứ tự. Có hai loại truy vấn:

• 1 l r x：Cho ~l,r,x~, với tất cả ~i\in[l,r]~, cập nhật ~a_i = a_i + x~ ;
• 2 l r：Cho ~l,r~, hãy tìm giá trị của ~\sum_{i=l}^ra_i~ (tức là ~a_l+a_{l+1}+\dots+a_r~).

Dữ liệu vào:

• Dòng đầu tiên chứa ~2~ số nguyên dương ~n,q~.
• Dòng thứ hai là ~n~ số nguyên ~a_1,a_2,\dots,a_n~.
• Dòng ~q~ tiếp theo, mỗi dòng là một trong hai truy vấn trên

Dữ liệu ra:

• Mỗi dòng ghi ra kết quả truy vấn loại 2 l r.

Input:

5 10
2 6 6 1 1
2 1 4
1 2 5 10
2 1 3
2 2 3
1 2 2 8
1 2 3 7
1 4 4 10
2 1 2
1 4 5 6
2 3 4

Output:

15
34
32
33
50

Giới hạn:

• ~1\le n,q\le 10^6,~
• ~|a_i|\le 10^6,~
• ~1\le l\le r\le n,~
• ~|x|\le 10^6.~