Truy vấn khủng khiếp (Horrible Queries)

Nguồn: SPOJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Duy trì một dãy ban đầu toàn số 0 với hai thao tác: cộng cùng một giá trị trên một đoạn và tính tổng một đoạn.

Input

Dòng đầu chứa hai số nguyên $n, q$. Mỗi trong $q$ dòng tiếp theo là một thao tác.

• 0 p r v: cộng $v$ vào mọi phần tử có chỉ số từ $p$ đến $r$. Nếu $p>r$, đoạn được hiểu từ $r$ đến $p$.
• 1 p r: in tổng trên đoạn giữa hai chỉ số $p$ và $r$, kể cả hai đầu.

Output

Với mỗi thao tác loại 1, in tổng cần tìm trên một dòng.

Subtask

• 20 điểm: $1\le n,q\le 50$.
• 30 điểm: $1\le n,q\le 5000$.
• 50 điểm: $1\le n,q\le 10^5$; $1\le p,r\le n$; $1\le v\le 10^7$.

Ví dụ

Input

5 5
0 1 3 2
1 1 5
0 2 5 1
1 3 4
1 1 2

Output

6
4
5

Giải thích

Sau lần cộng đầu, dãy là 2 2 2 0 0, nên truy vấn đầu cho $6$. Sau lần cộng thứ hai, dãy thành 2 3 3 1 1; hai truy vấn còn lại lần lượt cho $4$ và $5$.