Array Range Update and Sum Queries

You are given an array of integers and a series of queries. There are two types of queries:

1. Sum Query: of the form 1 l r. For this query, you need to compute the sum of the elements in the range ( [l, r] ) (1-indexed).

2. Update Query: of the form 2 l r v. In this query, you need to add an integer v to every element in the range ( [l, r] ). In mathematical terms, for all indices ( i ) such that ( l \le i \le r ), perform

[ A_i = A_i + v ]

This problem can be solved by employing a lazy propagation technique to handle range updates efficiently. The input is given from stdin and the output should be printed to stdout.

inputFormat

The first line contains two integers n and q, where n is the number of elements in the array and q is the number of queries. The second line contains n space-separated integers representing the array. Each of the next q lines represents a query in one of the following forms:

• 1 l r: Query the sum of elements from index l to r (1-indexed).
• 2 l r v: Add the value v to each element in the range [l, r] (1-indexed).

outputFormat

For each query of type 1, output a single line with the sum of the array segment from index l to r.## sample

6 4
1 2 3 4 5 6
1 1 6
2 2 5 10
1 1 6
1 2 4

21
61
39