In this problem you are to answer queries about weighted sum of a given array. Formally, you are given an array $a[1…n]$ of length $n$. You are to answer queries of two types:

• change on segment: given three integers $l,r,d$ you are to add $d$ to each elements $i$ of the array, such that $l≤i≤r$,
• compute weighted sum: given two integers $l,r$ you are to compute and print $a[l]⋅1+a[l+1]⋅2+… a[r]⋅(r−l+1)$.

The first line contains two integers $n,m\ (1≤n,m≤10^5)$, $n$ is the length of the array, and $m$ is the number of queries.

The second line contains integers $a[1],a[2],…,a[n]\ (−100≤a[i]≤100)$ — the given array.

Next $m$ lines contain queries, one per line. Query of the first type is given as "1 l r d" $(1≤l≤r≤n,\ −100≤d≤100)$, and query of the second type is given as "2 l r" $(1≤l≤r≤n)$.

For each query of the second type, print the answer on a separate line.