Description

As stated, given a sequence $\{a_i\}$, you need to perform the following two operations:

1. Add $k$ to every number in a given interval.
2. Find the sum of all numbers in a given interval.

Input Format

The first line contains two integers $n, m$, representing the number of elements in the sequence and the total number of operations.

The second line contains $n$ space-separated integers $a_i$, where the $i$-th integer is the initial value of the $i$-th element.

Each of the next $m$ lines contains $3$ or $4$ integers representing an operation, as follows:

1. 1 x y k: add $k$ to every number in the interval $[x, y]$.
2. 2 x y: output the sum of all numbers in the interval $[x, y]$.

Output Format

Output several lines of integers, which are the results of all type 2 operations.

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

11
8
20

Hint

For 15% of the testdata: $n \le 8$, $m \le 10$. For 35% of the testdata: $n \le {10}^3$, $m \le {10}^4$. For 100% of the testdata: $1 \le n, m \le {10}^5$, $a_i, k$ are positive, and the sum of the sequence at any time does not exceed $2\times 10^{18}$.

Sample Explanation.

Translated by ChatGPT 5