Range Update and Range Sum Query

You are given an array of n integers. Your task is to process q queries on this array. There are two types of queries:

• Update Query (Type 1): Given three additional integers l, r, and val, add val to every element from index l to r (1-based indexing).
• Sum Query (Type 2): Given two integers l and r, compute the sum of elements from index l to r. In mathematical terms, compute \(\sum_{i=l}^{r} a_i\).

After processing all queries, output the result for every sum query in the order they appear.

inputFormat

The first line contains two integers n and q — the number of elements in the array and the number of queries, respectively.
The second line contains n space-separated integers, representing the initial state of the array.
The next q lines each describe a query in one of the following formats:

• For an update query: 1 l r val
• For a sum query: 2 l r

Note that the array is 1-indexed.

outputFormat

For each sum query (Type 2), output the resulting sum on a new line.

## sample

5 1
1 3 5 7 9
2 1 3

9