Magical PE Class

There are \(n\) students standing in a line, each with a certain height. They all dislike the student at the front. Hence, for any segment of students, the happiness value of each student (except the first) in that segment is defined as follows: if the height of a student is greater than that of the first student of the segment, his happiness value equals the difference of their heights; otherwise his happiness value is \(0\). Formally, for a segment \([L,R]\) with base height \(h_L\), the happiness of a student at position \(i\) (with \(L < i \le R\)) is \(\max(0, h_i - h_L)\).

The PE teacher has a magic ability and can perform the following three types of operations:

1. Query: Given indices \(L\) and \(R\), determine the maximum happiness value among the students in the segment \([L,R]\).
2. Swap: Swap the positions of two students given their indices.
3. Update: For a segment \([L,R]\) and a given integer \(t\), update the heights by adding an arithmetic progression: add \(t\) to the first student, \(2t\) to the second, \(3t\) to the third, and so on.

You are required to process \(m\) operations on the students. For every query operation (Type 1), print the maximum happiness value for the given segment.

inputFormat

The first line contains two integers \(n\) and \(m\) \( (1 \leq n, m \leq 10^5)\): the number of students and the number of operations, respectively.

The second line contains \(n\) integers \(h_1, h_2, \ldots, h_n\) representing the initial heights of the students.

The following \(m\) lines each describe an operation in one of the following formats:

• Type 1 (Query): 1 L R — Query the segment \([L,R]\) for the maximum happiness value.
• Type 2 (Swap): 2 u v — Swap the students at positions \(u\) and \(v\).
• Type 3 (Update): 3 L R t — For positions from \(L\) to \(R\), add \(t\) to the first student, \(2t\) to the second, and so on.

It is guaranteed that all operations are valid and indices are 1-indexed.

outputFormat

For each query operation (Type 1), output a single integer on a new line denoting the maximum happiness value in the specified segment.

sample

5 5
100 90 110 105 120
1 1 5
2 2 5
1 1 5
3 2 4 5
1 2 4

20
20
0