Array Range Update and Query

Given an array of \( n \) integers and \( q \) operations, your task is to perform range updates and queries on the array. There are two types of operations:

• 1 l r x: For every index \( i \) from \( l \) to \( r \) (inclusive), add the integer \( x \) to \( a_i \).
• 2 l r: Output the sum of the elements \( a_l + a_{l+1} + \cdots + a_r \). That is, compute \( S = \sum_{i=l}^{r} a_i \).

You are required to implement these operations such that the update operation is processed immediately and the query operation prints the current sum of the specified range.

All indices are 1-indexed.

inputFormat

The first line contains two integers \( n \) and \( q \): the number of elements in the array and the number of operations to perform.

The second line contains \( n \) space-separated integers, which represent the initial array.

Each of the following \( q \) lines contains an operation in one of the following formats:

• 1 l r x — update operation: add \( x \) to each element from index \( l \) to \( r \) (inclusive).
• 2 l r — query operation: output the sum of elements from index \( l \) to \( r \) (inclusive).

outputFormat

For each query operation (type 2), output a single line containing the sum over the specified range.## sample

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

18
16