クオンは偏食がひどい。友人たちはクオンの偏食を直すため、クオンの好物であるピザの上に様々な具材を乗せようとしている。このピザは、最初のピースと最後のピースが繋がっている円形である。

クオンのピザの好み度は、連続するピザのピースの好み度の合計の最大値として定義される。また、各ピザのピースの好み度は、そのピースの上に乗っている具材の好み度の合計と等しい。何も具材が乗っていないピザのピースの好み度は0である。

ピザのピースを一つも選択しない場合をピザの好み度と呼ぶのは不適切であるため、ピザの好み度は一つ以上のピザのピースを選択する場合のみを考慮する。

最初にピザの上には何も具材が乗っていない。クオンの友人たちは合計 $Q$ 回にわたって、次の二つの行動のうち一つを行う。

• 1 $a$ $b$: $a$($1 \le a \le S$)番目のピースの上に具材の好み度が $b$($-10^9 \le b \le 10^9$)である具材を乗せる。
• 2: 現在のクオンのピザの好み度がいくらかを質問する。

入力

一行目にピザのピースの数 $S(1 \le S \le 200\,000)$ とクオンの友人たちの行動回数 $Q(1 \le Q \le 500\,000)$ が空白区切りで与えられる。

その後 $Q$ 行にわたって行動が与えられる。

行動 2 は少なくとも一回以上与えられる。

入力として与えられるすべての数は整数である。

出力

行動 2 が与えられるたびに、クオンのピザの好み度を出力せよ。

入出力例

入力 1

5 12
1 1 3
1 2 3
1 3 -5
2
1 5 3
2
1 4 3
2
1 4 -5
2
1 3 4
2

出力 1

6
9
12
9
9