# 糖果括号

预估时间限制：1 秒。内存限制：128 MB。

实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

糖果工坊把糖果和括号形糖衣串在一起，推出了可以从两端不断加料的试吃串。除了香甜的普通糖果，里面还混着芥末味、苦瓜味等怪味糖果：有的增加甜蜜值，有的反而扣分，括号形糖衣也有自己的甜蜜值。

顾客只能选取连续的一段，而且其中的括号必须完整匹配。工坊想在每次加料后找出甜蜜值最高的可选片段；如果实在没有合口味的，也可以一颗不选。

## 形式化问题描述

一个元素的类型为 $0$（左括号）、$1$（右括号）或 $2$（糖果），并带有整数甜蜜值，可以为负、零或正。串的甜蜜值是所有元素甜蜜值之和，括号的值也计入。

可匹配串恰好由以下规则生成：空串可匹配；单个糖果可匹配；在一个可匹配串外添加一对左右括号，所得串可匹配；两个可匹配串的连接可匹配。类型之外，甜蜜值不影响是否可匹配。

给定长度为 $N$ 的初始串，依次进行 $M$ 次操作。每次在当前串的左端或右端添加一个元素，修改持续生效。对子串取连续的一段，保持原顺序，不能跳过中间的负值元素；也允许取空串或整个串。求初始串和每次操作后，所有可匹配子串中的最大甜蜜值。空串的甜蜜值为 $0$ ，所以答案不会为负。

## 输入格式

第一行两个整数 $N,M$ .

第二行 $N$ 个整数，依次表示初始元素的类型；第三行 $N$ 个整数，依次表示它们的甜蜜值。若 $N=0$ ，这两行都是空行。

接下来 $M$ 行，每行三个整数 $position,type,value$ .其中 $position=0$ 表示添加到左端，$position=1$ 表示添加到右端；$type$ 是元素类型，$value$ 是其甜蜜值，可能带负号。

## 输出格式

输出 $M+1$ 行。第一行是初始串的答案，其余各行依次是对应操作后的答案。

## 样例

### 样例 1

### 输入

```text
2 2
2 2
-10 100
0 2 20
1 2 -200
```

### 输出

```text
100
110
110
```

### 样例 2

### 输入

```text
1 4
2
10
0 0 -8
1 1 -9
0 2 7
1 2 20
```

### 输出

```text
10
10
10
10
20
```

### 样例 3

### 输入

```text
0 4


1 1 4000000000
0 0 4000000000
0 2 0
1 2 3
```

### 输出

```text
0
0
8000000000
8000000000
8000000003
```

### 样例 4

### 输入

```text
3 0
0 2 1
-3 -2 -4
```

### 输出

```text
0
```

## 样例解释

第一组最初可以只选甜蜜值为 $100$ 的糖果。左端加入 $20$ 后，整个串的甜蜜值为 $20-10+100=110$ ；最后加入的 $-200$ 不必选择，答案仍为 $110$ .

第二组的糖果甜蜜值为 $10$ .两侧补齐括号后，整个可匹配串的甜蜜值为 $-8+10-9=-7$ ，但仍可只选里面的糖果，答案为 $10$ .左侧再加入 $7$ 后，不能跳过中间的左括号直接选两颗糖果。最后右侧加入 $20$ ，只选它或选择整个串都得到 $20$ .

第三组从空串开始。孤立的右括号无法匹配；补上左括号后，两个括号的值都计入，得到 $8000000000$ .

第四组所有元素的值都为负，选择空串得到 $0$ .

## 数据范围与保证

本题由 Codex（GPT-6）加强：所有元素（包括括号）的甜蜜值范围扩展为 $-4\times10^9\le value\le4\times10^9$ ，数据包含正负值混合的双端插入。

对所有数据，$0\le N,M\le10^6$ ，$position\in\{0,1\}$ ，$type\in\{0,1,2\}$ .初始元素的类型和值满足同样的范围。允许零甜蜜值、空初始串和零次操作；结果需要使用有符号 64 位整数保存。

| 分值比例 | 额外条件 |
| --- | --- |
| 20% | $N+M\le100$ |
| 20% | 所有元素的甜蜜值非负 |
| 20% | 所有元素的类型均为 $2$ |
| 40% | 无额外条件 |