Array Query Processing

You are given an array of (n) integers and (q) queries. There are two types of queries:

1. Update query: Given four integers: type, (l), (r), (k). For every index (i) such that (l \le i \le r), update the element as [ a[i] \leftarrow a[i] + k ]

2. Sum query: Given three integers: type, (l), (r). Compute the sum of the array elements from index (l) to index (r) (inclusive) and print the result.

Input format:

• The first line contains two integers (n) and (q), representing the number of elements in the array and the number of queries respectively.
• The second line contains (n) integers, representing the initial array elements.
• The following (q) lines each contain a query in one of the following formats:
  • For a type 1 query (update): 1 l r k
  • For a type 2 query (sum query): 2 l r

Output format:

For each query of type 2, output the computed sum on a new line. If there are no type 2 queries, print nothing.

inputFormat

The input is read from standard input (stdin) and follows the format:

(n) (q) (a_0) (a_1) ... (a_{n-1}) query1 query2 ...\nqueryq

Each query is either:

• 1 l r k for an update query, or
• 2 l r for a sum query.

outputFormat

For each type 2 query found in the input, print a single line containing the sum of the array elements from index (l) to index (r) (inclusive). The output should be sent to standard output (stdout).## sample

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

9
18
22