Bài 3

Cho dãy số $A$ gồm $N$ phần tử là các số nguyên dương $a_1, a_2, \dots, a_N$. Thực hiện lần lượt $Q$ thao tác trên dãy số đó, thao tác thứ $i$ sẽ có một trong hai loại như sau:

• Loại 1: $1\ p_i\ m_i\ x_i$ tăng giá trị phần tử tại vị trí $p_i$ tới vị trí $m_i$ của dãy số $A$ thêm $x_i$ đơn vị.
• Loại 2: $2\ u_i\ v_i$, tính tổng các phần tử của dãy số $A$ từ vị trí $u_i$ tới vị trí $v_i$.

Yêu cầu: Viết chương trình thực hiện $Q$ thao tác và ghi ra kết quả của các thao tác Loại 2.

Đọc từ file CAU3.INP

• Dòng đầu tiên ghi hai số nguyên dương $N, Q$ ($0 < N, Q \le 10^5$).
• Dòng thứ hai là một dãy số gồm $N$ số nguyên dương $a_i$ ($0 < a_i \le 10^{12}$), các số nằm trên một dòng và cách nhau một khoảng trắng.
• $Q$ dòng tiếp theo (từ dòng thứ 3 trở đi): với dòng thứ $i$ số đầu tiên là 1 hoặc 2.
  • Nếu số 1 thì theo sau là ba số nguyên dương $p_i, m_i$ và $x_i$ ($1 \le p_i \le m_i \le N$, $1 \le x_i \le 10^9$). Các số nằm trên một dòng và cách nhau một khoảng trắng.
  • Nếu số 2 thì theo sau là hai số nguyên dương $u_i$ và $v_i$ ($1 \le u_i \le v_i \le N$). Các số nằm trên một dòng và cách nhau một khoảng trắng.

Ghi ra file văn bản CAU3.OUT

• Gồm nhiều dòng, mỗi dòng ghi kết quả tương ứng của thao tác Loại 2.

• $0 < N, Q \le 10^5$; $0 < a_i \le 10^{12}$; $1 \le x_i \le 10^9$.