# Candy Brackets

Estimated time limit: 1 second. Memory limit: 128 MB.

The actual time limit is twice the slowest-case median runtime of the reference solution on the target judge, rounded up to a multiple of $0.5$ seconds. See the [benchmark environment](../../../docs/评测环境与性能.md).

## Story

A candy workshop strings together candies and bracket-shaped candy shells, adding new treats at either end. Alongside sweet favorites are unusual mustard and bitter-melon flavors: some add sweetness points, while others subtract them. The bracket-shaped shells have sweetness values of their own.

Customers may choose a contiguous segment only if its brackets match completely. After each addition, the workshop wants to find the sweetest eligible segment. Choosing nothing is allowed if none of the treats appeal.

## Formal Problem Statement

Each element has type $0$ (an opening bracket), $1$ (a closing bracket), or $2$ (a candy), and an integer sweetness value that may be negative, zero, or positive. A string's sweetness is the sum of all element values, including bracket values.

Matching strings are exactly those generated by these rules: the empty string matches; a single candy matches; enclosing a matching string in an opening and a closing bracket gives a matching string; concatenating two matching strings gives a matching string. Sweetness values do not affect matching.

Start with a string of length $N$ and perform $M$ operations. Each operation adds one element to the left or right end of the current string, and changes persist. A substring is a contiguous segment in the original order: negative elements in its interior cannot be skipped. The empty string and the entire string are allowed. Find the maximum sweetness of a matching substring initially and after each operation. The empty string has sweetness $0$ , so the answer is never negative.

## Input Format

The first line contains integers $N,M$ .

The second line contains the $N$ initial types, and the third contains their $N$ sweetness values, in order. If $N=0$ , both lines are empty.

Each of the next $M$ lines contains integers $position,type,value$ . Position $0$ means the left end and position $1$ the right end; $type$ is the element type and $value$ its sweetness, possibly with a minus sign.

## Output Format

Print $M+1$ lines. The first is the initial answer, followed by the answer after each operation in order.

## Samples

### Sample 1

### Input

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

### Output

```text
100
110
110
```

### Sample 2

### Input

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

### Output

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

### Sample 3

### Input

```text
0 4


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

### Output

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

### Sample 4

### Input

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

### Output

```text
0
```

## Sample Explanation

In the first sample, initially choose only the candy worth $100$ . After adding $20$ at the left, the whole string is worth $20-10+100=110$ . The final candy worth $-200$ can be excluded, leaving the answer at $110$ .

In the second sample, the candy is worth $10$ . After adding both brackets, the whole matching string is worth $-8+10-9=-7$ , but its inner candy can still be chosen for $10$ . Adding $7$ at the left does not allow choosing both candies while skipping the opening bracket between them. Finally, adding $20$ at the right gives answer $20$ , obtained either by that candy alone or by the entire string.

The third sample starts empty. A lone closing bracket does not match. Adding an opening bracket includes the values of both brackets, giving $8000000000$ .

In the fourth sample, all values are negative, so choose the empty string for $0$ .

## Constraints and Guarantees

This problem was strengthened by Codex (GPT-6): every element, including brackets, may have sweetness $-4\times10^9\le value\le4\times10^9$ , and the data include insertions at both ends with mixed positive and negative values.

For all inputs, $0\le N,M\le10^6$ , $position\in\{0,1\}$ , and $type\in\{0,1,2\}$ . Initial types and values have the same bounds. Zero sweetness, an empty initial string, and zero operations are allowed. Answers require signed 64-bit integers.

| Score share | Additional conditions |
| --- | --- |
| 20% | $N+M\le100$ |
| 20% | All element values are nonnegative |
| 20% | Every element has type $2$ |
| 40% | None |