Kuong 非常挑食。為了防止 Kuong 挑食，他的朋友們決定在他喜歡的披薩上放上各種配料。這張披薩是圓形的，第一片和最後一片披薩是相連的。

Kuong 的披薩偏好度定義為連續披薩切片偏好度總和的最大值。此外，單片披薩的偏好度等於該切片上所有配料的偏好度總和。沒有放任何配料的披薩切片，其偏好度為 0。

由於不選擇任何披薩切片來定義披薩偏好度並不合理，因此披薩的偏好度僅包含選擇一個或多個披薩切片的情況。

最初，披薩上沒有任何配料。Kuong 的朋友們總共會進行 $Q$ 次操作，每次操作為以下兩種之一：

• 1 $a$ $b$：在第 $a$ ($1 \le a \le S$) 片披薩上放上一種配料偏好度為 $b$ ($-10^9 \le b \le 10^9$) 的配料。
• 2：詢問 Kuong 目前披薩的偏好度是多少。

輸入格式

第一行包含披薩的切片數 $S$ ($1 \le S \le 200\,000$) 和朋友們的操作次數 $Q$ ($1 \le Q \le 500\,000$)，兩者以空白分隔。

接下來 $Q$ 行，每行給出一個操作。

操作 2 會至少出現一次。

輸入的所有數字皆為整數。

輸出格式

每當出現操作 2 時，請輸出 Kuong 的披薩偏好度。

範例

範例輸入 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