Horrible Queries

Source: SPOJ

Version: Phuoc Hung OJ Extended

Problem Statement

Maintain an initially zero array under range addition and range-sum queries.

Input

The first line contains integers $n,q$. Each of the next $q$ lines is an operation.

• 0 p r v: add $v$ to every element between positions $p$ and $r$, inclusive. If $p>r$, use the interval from $r$ to $p$.
• 1 p r: print the sum on that inclusive interval.

Output

For every type 1 operation, print the requested sum on its own line.

Subtasks

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

Examples

Input

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

Output

6
4
5

Explanation

After the first addition the array is 2 2 2 0 0, so the first answer is $6$. After the second addition it becomes 2 3 3 1 1, giving $4$ and $5$ for the remaining queries.