Magnetic Group Activation

We are given n groups of magical magnets. The i-th group is described by an integer parameter \(a_i\), and each group consists of \(2a_i\) magnets numbered from 1 to \(2a_i\). Each magnet can be either activated or not. However, these magnets behave strangely: unlike ordinary magnets, a group of magnets will magnetically "attract" (i.e. be arranged together smoothly) if and only if there exists an integer \(y\) with \(1\le y\le a_i\) such that no two activated magnets in that group have an absolute difference of exactly \(y\) (where the distance between magnets numbered \(i\) and \(j\) is \(|i-j|\)).

For example, consider the case \(a_i=2\), so the group has magnets {1,2,3,4}. If the activated set is {1,2} then note that the only possible distances among activated magnets is \(|1-2|=1\). Since for \(y=2\) no activated pair has distance 2, the group attracts. However, if the activated set is {1,2,3} then we have distances 1 (from 1 and 2, and also 2 and 3) and 2 (from 1 and 3). In this case, for every \(y\) in \([1,2]\) there is at least one pair with that distance, and therefore the group does not attract.

It turns out that in order for a group to attract, the maximum number of magnets that can be activated is exactly \(a_i\). Cute_QiQi wants to decorate by arranging all the groups (keeping members of the same group together) such that every group is attracted (i.e. satisfies the above condition) and the total number of activated magnets is maximized.

In addition, lzy will sometimes add extra magnets to some groups. The operations are as follows:

• Operation 1: 1 l r x. For every group with index in the interval \([l, r]\), add \(2x\) magnets. In terms of the parameter, this increases \(a_i\) by \(x\) for every \(i\) in \([l, r]\).
• Operation 2: 2 l r. Query the total number of activated magnets in groups with indices in \([l, r]\) when each group is activated optimally. Since the maximum activated magnet count for a group is its parameter \(a_i\), the answer is \(\sum_{i=l}^{r} a_i\).

Input Format:

The first line contains two integers \(n\) and \(q\), representing the number of groups and the number of operations, respectively. The second line contains \(n\) integers \(a_1,a_2,\dots,a_n\) where each \(a_i\) is the initial parameter of the i-th group (thus the group initially has \(2a_i\) magnets). Then \(q\) lines follow, each being one of the two types of operations in the format described above.

Output Format:

For each operation of type 2, output a single integer denoting the sum of the maximum activated magnets (i.e. the sum of the parameters) for all groups in the given range.

Constraints:

• \(1 \le n, q \le 10^5\)
• \(1 \le l \le r \le n\)
• \(1 \le a_i, x \le 10^9\)

Note: It can be proved that for a group with \(2a_i\) magnets, the maximum number of magnets that can be activated while satisfying the attraction condition is exactly \(a_i\).

inputFormat

The first line contains two space-separated integers \(n\) and \(q\). The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\), the initial parameters of the groups. Each of the next \(q\) lines represents an operation in one of the following formats:

• 1 l r x — add \(2x\) magnets (i.e. increase \(a_i\) by \(x\)) to every group in the index range \([l,r]\).
• 2 l r — output the sum \(\sum_{i=l}^{r} a_i\).

outputFormat

For each operation of type 2, print a single line containing the sum of the parameters \(a_i\) for groups in the specified range, which is equivalent to the maximum total number of activated magnets in that range.

sample

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

15
8
20

</p>