Truy vấn Đa thức

Cho một mảng gồm $n$ phần tử. Bạn cần xử lý $q$ truy vấn thuộc hai loại:

1. Cập nhật đa thức: Tăng giá trị đầu tiên trong đoạn $[a,b]$ thêm $1$, giá trị thứ hai thêm $2$, giá trị thứ ba thêm $3$, v.v. Nói cách khác, tăng vị trí $i$ ($a\le i\le b$) thêm $i-a+1$.
2. Tính tổng các giá trị trong đoạn $[a,b]$.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $q$: kích thước mảng và số truy vấn.

Dòng thứ hai chứa $n$ số nguyên $t_1,t_2,\dots ,t_n$: các giá trị ban đầu của mảng.

• $q$ dòng tiếp theo, mỗi dòng mô tả một truy vấn:

• 1 a b — cập nhật đa thức trên đoạn $[a,b]$

• 2 a b — tính tổng các giá trị trong đoạn $[a,b]$

Dữ liệu ra

Với mỗi truy vấn loại 2, in ra tổng các giá trị trong đoạn tương ứng.

Ràng buộc

• $1\le n,q\le 2·{10}^5$
• $1\le t_i\le {10}^6$
• $1\le a\le b\le n$

Ví dụ