Cho một dãy ~n~ số nguyên, ban đầu tất cả các phần tử có giá trị bằng ~0~. Cho ~q~ truy vấn gồm 2 loại như sau:

• ~1~ ~x~: Tăng toàn bộ dãy số lên từ vị trí ~x~ tới vị trí ~n~ một dãy ~1~, ~2~, ~3~, ~4~, ~5~, . . . (vị trí ~x~ tăng 1, vị trí ~x+1~ tăng 2, vị trí ~x+2~ tăng 3, . . .)
• ~2~ ~x~ ~y~: Đưa ra tổng các phần tử từ vị trí ~x~ tơi vị trí ~y~ của dãy,

Yêu cầu

Cho ~n~ và ~q~ truy vấn. Với mỗi truy vấn loại ~2~, in ra tổng của dãy con liên tiếp tương ứng.

Input

• Dòng đầu tiên chứa 2 số nguyên dương ~n~, ~q~ ~(1≤n≤10^6, 1≤q≤10^3)~ cách nhau một dấu cách.
• ~q~ dòng sau, mỗi dòng là một truy vấn có dạng ~1~ hoặc ~2~.

Output

Mỗi dòng tương ứng với kết quả của các truy vấn dạng ~2~.

Sample Input

5 3
2 4 5
1 1
2 2 4

Sample Output

0
9

Giải thích

Ban đầu dãy có 5 phần tử là [0, 0, 0, 0, 0].

Truy vấn đầu tiên yêu cầu tổng các phần tử từ vị trí 4 tới 5, kết quả là 0.

Truy vấn thứ hai yêu cầu tăng lên từ vị trí 1, nên dãy chuyển thành [1, 2, 3, 4, 5].

Truy vấn thứ ba yêu cầu tổng của các phần tử từ vị trí 2 tới vị trí 4, kết quả là ~2+3+4=9~.

Subtask

• Có 25% số test ứng với 25% số điểm có ~1≤n≤10^3~;
• Có 25% số test ứng với 25% số điểm có ~1≤n≤10^6~, mọi truy vấn dạng ~2~ có ~x=y~;
• Có 25% số test ứng với 25% số điểm có ~1≤n≤10^6~, chỉ có một truy vấn dạng ~2~ ở cuối cùng;
• 25% số test còn lại tương ứng với 25% số điểm không có giới hạn gì thêm.