13821382 SUSTech Online Judge
Problem 1382 --Tree array

1382: Tree array

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 13  Solved: 4
[Submit][Status][Web Board]

Description

For an array of length n {a1, a2, ... , an}.

There are q operations, for each operation:

If the operation value is 1 and {l, r, k}, then it will add k in {al, a(l+1), ... , ar} —>{al+k, a(l+1)+k, ... , ar+k}.

If the operation value is 2 and {l, r}, it will query the sum of {al, a(l+1), ... , ar}.


Input

The first line will consist of two integers N,Q ( 1 ≤ N,Q ≤ 1e5).

The second line will have n integers means {a1,a2,...,an}   (-1e5<=ai<=1e5)

The next q lines: i-th line have {1, l, r, k} or {2, l, r}.    (1<=l<=r<=N, -1e5<=K<=1e5)


Output

For each sum query whose operation value is 2, output the sum answer in a line.


Sample Input

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

Sample Output

30
13
6

HINT

Source

 

[Submit][Status]