Sequence Operation Queries

You are given an array \(a_1, a_2, \ldots, a_n\) and need to perform \(q\) operations. The operations are as follows:

1. Given an integer \(v\), update each element \(a_i\) to \(\min(a_i, v)\).
2. Update each element \(a_i\) to \(a_i + i\) (note that the array is 1-indexed).
3. Given two integers \(l\) and \(r\), output the sum \(\sum_{i=l}^{r} a_i\).

It is guaranteed that the input operations are valid. The result of each query (operation 3) should be output on a separate line.

inputFormat

The first line contains two integers (n) and (q) representing the number of elements in the array and the number of operations, respectively. The second line contains (n) integers representing the initial array (a). Each of the next (q) lines contains one operation in one of the following formats:

• 1 v: For every \(i\) (\(1 \le i \le n\)), update \(a_i = \min(a_i, v)\).
• 2: For every \(i\) (\(1 \le i \le n\)), update \(a_i = a_i + i\).
• 3 l r: Output \(\sum_{i=l}^{r} a_i\), where \(1 \le l \le r \le n\).

outputFormat

For every query operation (type 3), output the result of the query on a new line.

sample

5 5
5 3 8 6 1
3 1 5
1 4
3 2 4
2
3 1 3

23
11
17