Cộng đoạn, tổng đoạn

Cho mảng $a_1,a_2,\dots ,a_n$ và $q$ thao tác. Có hai loại thao tác:

• Cộng đoạn: 1 l r v — với mỗi $i\in [l,r]$ tăng $a_i$ thêm $v$.
• Hỏi tổng đoạn: 2 l r — in ra $a_l+a_{l+1}+\dots +a_r$.

Dữ liệu vào

• Dòng đầu: hai số nguyên $n$ và $q$.
• Dòng thứ hai: $n$ số nguyên $a_1,\dots ,a_n$.
• $q$ dòng tiếp theo, mỗi dòng mô tả một thao tác:
  • 1 l r v: cộng $v$ vào $a_l,\dots ,a_r$.
  • 2 l r: hỏi tổng đoạn $[l,r]$.

Dữ liệu ra

Với mỗi thao tác loại $2$ in một dòng — tổng đoạn tương ứng.

Ràng buộc

• $1\le n,q\le 2·{10}^5$
• $1\le l\le r\le n$
• $|a_i|,|v|\le {10}^9$
• Giá trị các phần tử và tổng đoạn nằm trong phạm vi số nguyên có dấu 64-bit.

Ví dụ

Ghi chú

• Tổng đoạn có thể âm và rất lớn về độ lớn; dùng long long (C++) hoặc số nguyên Python.
• Mảng dùng chỉ số $1$.