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:
import sys
input = sys.stdin.readline


class BIT():
    """区間加算、区間取得クエリをそれぞれO(logN)で答える
    add: 区間[l, r)にvalを加える
    get_sum: 区間[l, r)の和を求める
    l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit0 = [0] * (n + 1)
        self.bit1 = [0] * (n + 1)

    def _add(self, bit, i, val):
        i = i + 1
        while i <= self.n:
            bit[i] += val
            i += i & -i

    def _get(self, bit, i):
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(self.bit0, l, -val * l)
        self._add(self.bit0, r,  val * r)
        self._add(self.bit1, l,  val)
        self._add(self.bit1, r, -val)

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._get(self.bit0, r) + r * self._get(self.bit1, r) \
               - self._get(self.bit0, l) - l * self._get(self.bit1, l)


n, q = map(int, input().split())
query = [list(map(int, input().split())) for i in range(q)]
bit = BIT(n)

for i in range(q):
    if query[i][0] == 0:
        _, l, r, x = query[i]
        bit.add(l-1, r, x)
    else:
        _, l, r = query[i]
        print(bit.get_sum(l-1, r))