Graveyard Feng Shui Operations

You are given a graveyard that consists of n tombstones. Among them, there is one main tombstone (numbered 1) and n-1 secondary tombstones (numbered 2, 3, ..., n). Each tombstone has an initial feng shui value. Over the course of many years, the graveyard keeper performs a sequence of operations. The operations are:

• 1 l r k: Increase the feng shui values for every tombstone in the interval \([l, r]\) by \(k\).
• 2 k: Increase the feng shui value of the main tombstone (tombstone 1) by \(k\).
• 3 k: Decrease the feng shui value of the main tombstone by \(k\) (i.e. add \(-k\)).
• 4 l r: Query the sum of feng shui values for tombstones in the interval \([l, r]\).
• 5: Query the feng shui value of the main tombstone (tombstone 1).

You are to process the operations in the order given. For queries (operations of type 4 and 5), print the correct result. It is guaranteed that there will be at least 1 query operation.

Note: All formulas are given in LaTeX format. For example, \([l, r]\) and \(k\) are used as parameters in the operations.

inputFormat

The input begins with two integers n and m (1 \(\leq n, m \leq 10^5\)), where n is the number of tombstones and m is the number of operations.

The next line contains n integers, representing the initial feng shui values of the tombstones (from tombstone 1 to tombstone n).

Then m lines follow, each representing an operation. The operations are encoded as follows:

• For operation type 1: the line contains: 1 l r k
• For operation type 2: the line contains: 2 k
• For operation type 3: the line contains: 3 k
• For operation type 4: the line contains: 4 l r
• For operation type 5: the line contains: 5

It is guaranteed that the input is valid.

outputFormat

For each query operation (types 4 and 5), output the corresponding result on a new line.

sample

5 7
10 20 30 40 50
1 2 4 10
4 1 3
2 5
5
3 3
4 1 5
4 2 2

80
15
182
30