Cộng Đoạn, Tính Tổng

Input gồm nhiều test độc lập. Trong mỗi test có một mảng $a$ gồm $n$ phần tử, ban đầu tất cả đều bằng $0$.

Bạn cần xử lý $q$ thao tác theo thứ tự:

• $0$ $l$ $r$ $v$: cộng $v$ vào mọi phần tử $a_l,a_{l+1},\dots ,a_r$;
• $1$ $l$ $r$: tính tổng $a_l+a_{l+1}+\cdots +a_r$.

Khi chuyển sang test mới, mọi dữ liệu của test trước bị bỏ và mảng lại bắt đầu từ toàn số $0$.

Input

• Dòng đầu chứa số nguyên $T$, số lượng test.
• Mỗi test bắt đầu bằng một dòng chứa hai số nguyên $n$ và $q$, sau đó là $q$ dòng thao tác theo một trong hai dạng trên.

Output

• Với mỗi thao tác loại $1$ của mọi test, in tổng được hỏi trên một dòng theo đúng thứ tự xuất hiện.

Constraints

• $1\le T\le 10$.
• Trong mỗi test: $1\le n,q\le 10^5$.
• $1\le l\le r\le n$.
• Với thao tác loại $0$: $1\le v\le 10^7$.
• Mọi giá trị tích lũy và tổng đều nằm trong miền của số nguyên có dấu $64$-bit.

Scoring

• Subtask $1$ ($50\%$ số điểm): $T\le 5$ và $n,q\le 500$ trong mỗi test.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

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

0
6
11
12
5