题目描述

長さ $2N$ の数列 $a,b$ が与えられます。$i$ 番目の要素はそれぞれ $a_i,b_i$ です。 すぬけくんはこの $2$ つの数列を使って長さ $2N$ の バランスの取れた括弧列 のペア $(s,t)$ の 美しさ を計算する仕事をしています。 美しさは以下のように計算されます。

• $X=0$ とする
• $1$ 以上 $2N$ 以下の全ての $i$ について、$s_i\ =\ t_i$ ならば $a_i$ を、そうでなければ $b_i$ を $X$ に加算する
• 最終的な $X$ の値が $(s,t)$ の美しさである

$Q$ 個のクエリが与えられるので順番に処理してください。 $i$ 番目のクエリでは $a_{p_i}$ を $x_i$ に、$b_{p_i}$ を $y_i$ に更新した後、バランスの取れた括弧列のペアの美しさとしてありうる値の最大値を求めてください。

この問題において、以下に示されるいずれかのみがバランスの取れた括弧列として定義されます。

• 空文字列
• バランスの取れた括弧列 $s$ について (,$s$, ) をこの順番で連結した文字列
• バランスの取れた括弧列 $s,t$ について $s,t$ をこの順番で連結した文字列

输入格式

入力は以下の形式で標準入力から与えられる。

$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$

输出格式

答えを $Q$ 行に出力せよ。$i$ 行目には $i$ 番目のクエリに対する応答を出力せよ。

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

15
15

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

311
312
260
286
296
292
327

提示

制約

• $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$
• 与えられる入力は全て整数

部分点

• $200$ 点分のデータセットでは $N\ \leq\ 5,Q\ \leq\ 10$ が成立する
• $300$ 点分のデータセットでは $Q=1$ が成立する

Sample Explanation 1

- $1$ 番目のクエリにより、$a=(1,4,7,3),b=(4,6,3,3)$ となります。$(s,t)\ =($()(),()()$)$ のとき、美しさが $15$ となり、これが最大です。 - $2$ 番目のクエリにより、$a=(1,4,2,3),b=(4,6,5,3)$ となります。$(s,t)\ =($()(),(())$)$ のとき、美しさが $15$ となり、これが最大です。