It is time for another physical education class, and $n$ students are standing in a row. They all dislike the student at the first position. Therefore, any student behind the first one who is taller than the first student generates a "happiness value," which is equal to their height minus the height of the first student. Students who are shorter than or equal to the first student generate a happiness value of $0$.

Now, the PE teacher arrives. Possessing magical powers, the teacher can perform the following three types of operations:

1. Query the maximum happiness value in a given range.
2. Swap the positions of two students.
3. Select a range of people and increase the height of the first person by $t$, the second by $2t$, the third by $3t$, and so on.

However, the PE teacher cannot count, so he has come to you. For each query, he needs you to help him find that value.

Input

The first line contains two integers $n$ and $m$, representing $n$ students and $m$ operations.

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

The next $m$ lines each start with an integer $type$, indicating the type of operation:

• If $type=1$, it is followed by two integers $l$ and $r$, representing a query for the maximum happiness value in the range $[l, r]$.
• If $type=2$, it is followed by two integers $a$ and $b$, representing the swapping of the students at positions $a$ and $b$.
• If $type=3$, it is followed by three integers $l, r, t$, representing an increase in the height of the student at position $l$ by $t$, the student at $l+1$ by $2t$, ..., and the student at $r$ by $(r-l+1)t$.

Output

For each query of type $1$, output the answer in the order they appear.

Examples

Input 1

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

Output 1

722
722
722
719

Subtasks

• For $20\%$ of the data, $1 \le n, m \le 5 \times 10^3$.
• An additional $10\%$ of the data does not contain the third type of operation.
• An additional $20\%$ of the data does not contain the second type of operation.
• For $100\%$ of the data, $1 \le n, m \le 10^5$, $0 \le t \le 10^4$, $1 \le a_i \le 10^8$.