AT_aalc001_i 連続部分列

長さ $ N $ の整数列 $ A=(A_1,A_2,\ldots,A_N) $ が与えられます。 クエリを $ Q $ 個処理してください。クエリは以下の $ 2 $ 種類のいずれかです。 - `1 i x`： $ A_i $ を $ x $ に変更する。 - `2 l r`：数列 $ (A_l,A_{l+1},\ldots,A_r) $ から、要素を共有しない非空の連続部分列を $ 0 $ 個以上 $ 2 $ 個以下選ぶ。選んだ連続部分列に含まれる要素の総和としてあり得る最大値を出力する。 ここで、数列 $ (A_l,A_{l+1},\ldots,A_r) $ の非空の連続部分列とは、整数 $ s,t $ を $ l\leq s\leq t\leq r $ を満たすように選んだときの $ (A_s,A_{s+1},\ldots,A_t) $ のことです。 また、 $ 2 $ 個の連続部分列を選ぶ場合、それらに含まれる位置が重複してはいけません。

入力は以下の形式で標準入力から与えられる。 > $ 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 はじめの $ 2 $ 種類目のクエリでは、 $ (A_3,A_4,A_5)=(3,-1,2) $ と $ (A_7)=(5) $ を選ぶと、要素の総和は $ 9 $ になります。これが最大です。 $ 4 $ 番目のクエリでは、 $ A $ は $ (4,-5,3,10,2,-6,5) $ です。このとき、 $ (A_3,A_4,A_5) $ と $ (A_7) $ を選ぶと、要素の総和は $ 20 $ になり、これが最大です。 $ 7 $ 番目のクエリでは、どの連続部分列も選ばないと要素の総和は $ 0 $ になります。これが最大です。 ### Constraints - $ 1\leq N\leq 10^5 $ - $ 1\leq Q\leq 10^5 $ - $ -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\leq r\leq N $ - 入力される数値はすべて整数