AT_aalc001_s 絶対値

長さ $ N $ の整数列 $ A=(A_1,A_2,\ldots,A_N) $ が与えられます。 クエリを $ Q $ 個処理してください。クエリは以下の $ 2 $ 種類のいずれかです。 - `1 i x`： $ A_i $ を $ x $ に変更する。 - `2 l r`：整数 $ m $ と整数列 $ (i_1,i_2,\ldots,i_m) $ を $ 3 \leq m $ かつ $ l \leq i_1 \lt i_2 \lt \cdots \lt i_m \leq r $ を満たすように選べるとき、次の値の最大値を出力する。 \\\[ \\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 $

$ 2 $ 種類目のクエリの個数を $ q $ として、 $ q $ 行出力せよ。 $ j $ 行目には、 $ j $ 番目の $ 2 $ 種類目のクエリに対する答えを出力せよ。

### Sample Explanation 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 $ に変更されます。 ### Constraints - $ 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 $ - 入力される数値はすべて整数