Center Stage

Jeonghu, a member of Nacoder's 39th class, wants to present a Nacoder stage at Solde Festival 2022. The stage is titled 'Sequence and Query 333'. Students numbered 1 to $N$ stand in a line and perform $Q$ actions designed by Jeonghu. Each action is one of two types. Each student has a charm represented by one integer.

• A type 1 action changes the charm of student $x_i$ to $y_i$.
• A type 2 action sends three different students from $l_i$ to $r_i$ onto the stage. For $l_i \le a < b < c \le r_i$, students $a$, $b$, and $c$ perform the action.

The more outstanding the center's charm is, the higher the stage charm becomes. Let $A_i$ be the charm of student $i$. The stage charm is computed as $A_b - A_a - A_c$.

For each action, pick three students to help Jeonghu reach the maximum stage charm.

The first line contains two integers $N$ and $Q$, separated by a space. The second line contains $N$ integers separated by spaces. The $i$-th number is the charm $A_i$ of student $i$. From the third line to line $Q + 2$, each line contains three integers separated by spaces. The first number in each line is the action type. For a type 1 action, $x_i$ and $y_i$ follow. For a type 2 action, $l_i$ and $r_i$ follow.

For each type 2 action, print the maximum stage charm on its own line.

• $3 \le N \le 333{,}333$
• $1 \le Q \le 333{,}333$
• $1 \le x_i \le N$
• $-33{,}333{,}333 \le A_i, y_i \le 33{,}333{,}333$
• $1 \le l_i, r_i \le N$
• $l_i + 2 \le r_i$
• All given numbers are integers.
• At least one type 2 action is given.