Description

It is time for another PE class. There are $n$ students standing in a row. They all dislike the student at the first position. For any student behind the first one, if they are taller than the first student, they gain a happiness value equal to their height minus the height of the first student. If a student is shorter than the first student, their happiness value is $0$.

Now the PE teacher comes with magical powers and can perform the following three operations:

1. Query the maximum happiness value within a given interval.
2. Swap two students.
3. Select an interval and add $t$ to the first person in the interval, $2t$ to the second, $3t$ to the third, and so on.

However, the teacher cannot count well, so he asks you to answer each query.

For clarity, for an interval $[l, r]$, define the happiness of position $i$ ($l \le i \le r$) as $\max(0, a_i - a_l)$. Operation $1$ asks for the maximum of these values over $i \in [l, r]$.

Input Format

The first line contains two integers $n, m$, the number of students and the number of operations.

The second line contains $n$ integers, the heights $a_i$ of the students in order.

Each of the following $m$ lines starts with an integer $type$ indicating the operation:

• If $type = 1$, then two integers $l, r$ follow, asking for the maximum happiness value in interval $[l, r]$ as defined above.
• If $type = 2$, then two integers $a, b$ follow, indicating to swap the students at positions $a$ and $b$.
• If $type = 3$, then three integers $l, r, t$ follow, indicating that for every $i$ with $l \le i \le r$, add $(i - l + 1) \times t$ to $a_i$.

Output Format

For each query, output the answer to every operation $1$ in order.

6 7
109 827 100 530 10 826
3 1 6 1
2 2 6
1 2 4
1 2 3
2 2 6
1 2 6
1 2 5

722
722
722
719

Hint

Constraints

• For $20\%$ of the testdata, $1 \le n, m \le 5 \times 10^3$.
• Additionally, in $10\%$ of the testdata, there is no operation $3$.
• Additionally, in $20\%$ of the testdata, there is no operation $2$.
• For $100\%$ of the testdata, $1 \le n, m \le 10^5$, $0 \le t \le 10^4$, $1 \le a_i \le 10^8$.

Translated by ChatGPT 5