Tăng dần vị trí

Bạn được giao nhiệm vụ xử lý một mảng gồm \(N\) số nguyên dương. Trải qua thời gian, mảng này liên tục bị can thiệp với các thao tác "tăng có quy luật" hoặc "truy vấn tổng đoạn".

Cụ thể, bạn cần thực hiện \(Q\) truy vấn theo hai loại sau:

• Loại 1: 1 a b --- Tăng đoạn \([a, b]\) một cách đặc biệt: phần tử ở vị trí \(a\) tăng thêm \(1\), vị trí \(a+1\) tăng thêm \(2\), ..., vị trí \(b\) tăng thêm \((b - a + 1)\).
• Loại 2: 2 a b --- Trả về tổng các phần tử trong đoạn \([a, b]\) hiện tại của mảng.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(Q\) \((1 \leq N, Q \leq 2 \cdot 10^5)\) --- kích thước của mảng và số lượng truy vấn.
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \ldots, A_N\) \((1 \le A_i \le 10^9)\) --- các phần tử ban đầu của mảng.

• \(Q\) dòng tiếp theo, mỗi dòng là một truy vấn có định dạng:

• 1 a b --- tăng đoạn \([a, b]\) theo quy luật như mô tả trên.

• 2 a b --- truy vấn tổng đoạn \([a, b]\).

Output

Với mỗi truy vấn loại 2, in ra một dòng chứa kết quả --- tổng các phần tử từ vị trí \(a\) đến \(b\) trong mảng hiện tại.

Example

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

17
32

Scoring

• Subtask 1 (50% số điểm): \(N, Q \leq 2000\).
• Subtask 2 (50% số điểm): Không có ràng buộc gì thêm.