You have an array of ~N~ integers, initialized all to zero to begin with. Support two operations.

INCREMENT l r a - For each index ~i~ between ~l~ and ~r~, increase the ~i~th element of the array by ~a \cdot (i-l+1)~.

SUM l r - Compute the sum of the integers between indices ~l~ and ~r~, inclusive.

Constraints

~1 \le N \le 10^6~

~1 \le Q \le 10^5~

~1 \le l_i \le r_i \le N~

~1 \le a_i \le 5~

Input Specification

The first line contains two positive integers, ~N~ and ~Q~.

The next ~Q~ lines each contain a sequence of positive integers. If the first integer in the line is ~1~, then three integers follow, ~l_i~, ~r_i~, and ~a_i~, indicating an INCREMENT operation.

Otherwise, the first integer in the line is ~2~, and then two integers follow, ~l_i~ and ~r_i~, indicating a SUM operation.

Output Specification

For each SUM operation, output on its own line the result of the query. The data will be set such that this fits in a signed 32-bit integer.

Sample Input

3 4
1 2 3 2
2 1 1
2 2 2
2 3 3

Sample Output

0
2
4