Problem: Write a program which manipulates a sequence A = {a1, a2, . . . , an} with the following operations:

* add(s, t, x): add x to as, as+1, ..., at.
* getSum(s, t): report the sum of as, as+1, ..., at.



Note that the initial values of ai (i = 1, 2, . . . , n) are 0.

Constraints

* 1 ≤ n ≤ 100000
* 1 ≤ q ≤ 100000
* 1 ≤ s ≤ t ≤ n
* 0 ≤ x < 1000

Input


n q
query1
query2
:
queryq


In the first line, n (the number of elements in A) and q (the number of queries) are given. Then, ith query queryi is given in the following format:


0 s t x


or


1 s t


The first digit represents the type of the query. '0' denotes add(s, t, x) and '1' denotes getSum(s, t).

Output

For each getSum operation, print the sum;

Examples

Input

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


Output

4
8


Input

4 3
1 1 4
0 1 4 1
1 1 4


Output

0
4

Solution (in PYTHON3):

Solution:
class BinaryIndexedTree():
    def __init__(self, n):
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


N, Q = [int(_) for _ in input().split()]
Query = [input().split() for _ in range(Q)]
BIT0 = BinaryIndexedTree(N + 1)
BIT1 = BinaryIndexedTree(N + 1)
#sum'([0,p))=sum([0,p)) if p<a
#sum'([0,p))=sum([0,p))+p*x-(a-1)*x if a<=p<b
#sum'([0,p))=sum([0,p))+(b-(a-1))*x if b<=p
for query in Query:
    c, *array = query
    array = list(map(int, array))
    if c == '1':
        a, b = array
        a -= 1
        res = 0
        res += b * BIT1.sum(b) + BIT0.sum(b)
        res -= a * BIT1.sum(a) + BIT0.sum(a)
        print(res)
    else:
        a, b, x = array
        b += 1
        BIT1.add(a, x)
        BIT0.add(a, -(a - 1) * x)
        BIT1.add(b, -x)
        BIT0.add(b, (b - 1) * x)