Process Queries on a List

You are given a list of n integers and q queries. There are two types of queries:

• 0 A B V: For every index i in the range A \leq i \leq B (0-indexed), add the integer V to the element at index i.
• 1 A B: Compute the sum $$S = \sum_{i=A}^{B} a_i$$ where a_i is the current value of the element at index i. Output the sum.

The list is modified in-place by the update queries. You must process the queries in the given order. All input is provided via stdin and all required output should be printed to stdout (one sum per line for each sum query).

inputFormat

The first line of input contains two space-separated integers n and q, the number of elements in the list and the number of queries, respectively.

The second line contains n space-separated integers representing the initial values of the list.

The following q lines each contain a query. A query is either of the form 0 A B V (to update the list) or 1 A B (to perform a sum query). The indices are 0-indexed.

outputFormat

For each query of the second type (i.e. queries starting with 1), output the computed sum on a new line.

## sample

5 4
1 2 3 4 5
0 1 3 10
1 0 4
0 2 4 5
1 1 3

45
49

</p>