Tèo có một hàng gồm \(N\) chậu hoa được xếp thẳng hàng và đánh số từ \(1\) đến \(N\). Ban đầu, chậu hoa thứ \(i\) có chiều cao là \(A_i\). Để chăm sóc hoa tốt nhất, Tèo thường xuyên thực hiện hai công việc sau:

• 1 pos val: Tèo bồi thêm đất làm tăng chiều cao của chậu hoa tại vị trí \(pos\) thêm một lượng là \(val\).
• 2 l r: Tèo muốn đo tổng chiều cao của tất cả các chậu hoa nằm trong khoảng từ vị trí \(l\) đến vị trí \(r\).

Hãy viết chương trình giúp Tèo hoàn thành việc theo dõi chiều cao các chậu hoa.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) là chiều cao ban đầu của các chậu hoa (\(0 \le a_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa một truy vấn thuộc một trong hai định dạng trên (\(1 \le pos \le N\), \(1 \le l \le r \le N\), \(0 \le val \le 10^9\)).

Định dạng đầu ra

• Với mỗi truy vấn loại 2, in ra tổng chiều cao tìm được trên một dòng riêng biệt.

Ví dụ

Input:

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

Output:

9
14