센터가 돋보여야 해

나코더 39기 부원인 정후는 2022년 솔대제에서 나코더의 무대를 선보이려고 한다. 무대의 이름은 '수열과 쿼리 333'이다. 1번부터 $N$번까지 일렬로 서 있는 학생들이 정후가 만든 $Q$가지 동작을 보여 준다. 각 동작은 두 종류 중 하나이고, 각 학생은 정수 하나로 나타내는 매력을 가진다.

• 첫 번째 종류의 동작은 $x_i$번 학생의 매력을 $y_i$로 바꾼다.
• 두 번째 종류의 동작은 $l_i$번 학생부터 $r_i$번 학생 사이에서 서로 다른 학생 세 명을 무대에 내보낸다. $l_i \le a < b < c \le r_i$를 만족하는 $a$번, $b$번, $c$번 학생이 나와 동작을 마친다.

센터의 매력이 독보적일수록 무대의 매력이 커진다. $i$번 학생의 매력을 $A_i$라고 할 때, 무대의 매력은 $A_b - A_a - A_c$로 계산한다.

정후를 위해 각 동작마다 세 명을 골라 무대의 매력의 최댓값을 구하자.

첫째 줄에 학생의 수 $N$과 동작의 수 $Q$가 공백으로 구분되어 주어진다. 둘째 줄에는 $N$개의 정수가 공백으로 구분되어 주어진다. $i$번째 수는 $i$번 학생의 매력 $A_i$이다. 셋째 줄부터 $Q + 2$째 줄까지 동작 정보가 세 정수로 주어진다. 각 행의 첫 번째 수는 동작의 종류이다. 첫 번째 종류의 동작에서는 이어서 $x_i$와 $y_i$가 주어지고, 두 번째 종류의 동작에서는 이어서 $l_i$와 $r_i$가 주어진다.

두 번째 종류의 동작이 주어질 때마다 무대의 매력의 최댓값을 한 줄에 하나씩 출력한다.

• $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$
• 주어지는 모든 수는 정수이다.
• 두 번째 종류의 동작이 적어도 하나 주어진다.