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