AT_aalc001_s.Absolute Value

给你一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$。

你需要处理 $Q$ 个查询，每个查询为以下两种类型之一：

• 1 i x：将 $A_i$ 修改为 $x$。
• 2 l r：对所有满足 $3 \leq m$ 且 $l \leq i_1 \lt i_2 \lt \cdots \lt i_m \leq r$ 的整数 $m$ 和整数序列 $(i_1,i_2,\ldots,i_m)$，输出下列表达式的最大值：

\[ \sum_{k=1}^{m-2} \left|A_{i_k}+2A_{i_{k+1}}+3A_{i_{k+2}}\right| \]

输入从标准输入中按以下格式给出：

$N$ $Q$
$A_1$ $A_2$ $\ldots$ $A_N$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

每个查询以如下两种格式之一给出：

$1$ $i$ $x$

$2$ $l$ $r$

设 $q$ 为类型 $2$ 的查询数量。输出 $q$ 行，其中第 $j$ 行应包含第 $j$ 个类型 $2$ 查询的答案。

样例 1 解释：
对于查询 $1$，唯一的选择是 $m=3$，$(i_1,i_2,i_3)=(1,2,3)$，所求值为 $6$。

对于查询 $2$，选择 $m=4$，$(i_1,i_2,i_3,i_4)=(1,2,3,5)$ 可得到值 $16$，这是最大值。

查询 $3$ 将 $A_2$ 修改为 $4$。

约束条件

• $1 \leq N \leq 5 \times 10^4$
• $1 \leq Q \leq 5 \times 10^4$
• $-10^9 \leq A_i \leq 10^9$
• 对于类型 $1$ 的查询，满足 $1 \leq i \leq N$，$-10^9 \leq x \leq 10^9$
• 对于类型 $2$ 的查询，满足 $1 \leq l \lt r \leq N$，且 $r-l \geq 2$
• 输入中的所有数值均为整数。