Range Update and Range Sum Query

Given an initial sequence \(\{a_i\}\), you need to perform two types of operations:

• Operation 1: For a given interval, add a constant \(k\) to every element. In other words, update \(a_i = a_i + k\) for all \(l \le i \le r\).
• Operation 2: For a given interval, query the sum of all numbers in that range.

The operations are given in the input using the following format:

1 l r k   // Add k to each element in the interval [l,r]
2 l r     // Output the sum of the elements in the interval [l,r]

Note: The indices in the input are 1-indexed.

inputFormat

The first line contains two integers, \(n\) and \(q\), representing the number of elements in the sequence and the number of operations, respectively.

The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\) that form the initial sequence.

The next \(q\) lines each contain an operation, either of the following two forms:

1 l r k
2 l r

For an operation of type 1, add \(k\) to each element from index \(l\) to \(r\). For an operation of type 2, output the sum of elements from index \(l\) to \(r\).

outputFormat

For each operation of type 2, print the sum of the specified subarray on a new line.

sample

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

15
18
16