Problem Description

Given two sequences $a$ and $b$ of length $2N$, where the $i$-th element is $a_i$ and $b_i$ respectively. Snuke is tasked with calculating the beauty of pairs of balanced parentheses sequences $(s, t)$ using these sequences. The beauty is calculated as follows:

• Initialize $X = 0$
• For all $i$ from $1$ to $2N$, if $s_i = t_i$, add $a_i$ to $X$; otherwise, add $b_i$ to $X$
• The final value of $X$ is the beauty of $(s, t)

You are given $Q$ queries to process sequentially. In the $i$-th query, update $a_{p_i}$ to $x_i$ and $b_{p_i}$ to $y_i$, then find the maximum possible beauty of a pair of balanced parentheses sequences.

In this problem, only the following are defined as balanced parentheses sequences:

• The empty string
• For a balanced parentheses sequence $s$, the string formed by concatenating (, $s$, and ) in this order
• For balanced parentheses sequences $s$ and $t$, the string formed by concatenating $s$ and $t$ in this order

Input Format

The input is given from the standard input in the following format:

$ N $ $ Q $ $ a_1 $ $ a_2 $ $ ... $ $ a_{2N} $ $ b_1 $ $ b_2 $ $ ... $ $ b_{2N} $ $ p_1 $ $ x_1 $ $ y_1 $ $ : $ $ p_Q $ $ x_Q $ $ y_Q $

Output Format

Output the answers in $Q$ lines. The $i$-th line should contain the response to the $i$-th query.

Sample Input and Output

Sample Input #1

2 2
1 1 7 3
4 2 3 3
2 4 6
3 2 5

Sample Output #1

15
15

Sample Input #2

7 7
34 -20 -27 42 44 29 9 11 20 44 27 19 -31 -29
46 -50 -11 20 28 46 12 13 33 -22 -48 -27 35 -17
7 27 34
12 -2 22
4 -50 -12
3 -32 15
8 -7 23
3 -30 11
4 -2 23

Sample Output #2

311
312
260
286
296
292
327

Notes/Hints

Constraints

• $1 \leq N, Q \leq 10^5$
• $-10^9 \leq a_i, b_i, x_i, y_i \leq 10^9$
• $1 \leq p_i \leq 2N$
• All given inputs are integers

Partial Points

• For a dataset worth 200 points, $N \leq 5, Q \leq 10$ holds
• For a dataset worth 300 points, $ Q = 1 $ holds

Sample Explanation 1

• After the first query, $ a = (1, 4, 7, 3), b = (4, 6, 3, 3) $. When $(s, t) = (`()()`, `()()`) $, the beauty is $ 15 $, which is the maximum.
• After the second query, $ a = (1, 4, 2, 3), b = (4, 6, 5, 3) $. When $(s, t) = (`()()`, `(())`) $, the beauty is $ 15 $, which is the maximum.

见题面 Input 部分

见题面 Output 部分