问题描述

给定两个长度为 $2N$ 的序列 $a$ 和 $b$。$a$ 和 $b$ 中的第 $i$ 个元素分别为 $a_i$ 和 $b_i$。通过使用这些序列，Snuke 正在计算长度为 $2N$ 的平衡括号序列对的 美丽度（如下所定义）。对于一个对 $(s,t)$ 的美丽度如下计算：

• 设 $X=0$。
• 对于每个 $i$，$1$ 到 $2N$（包括两端），如果 $s_i = t_i$ 则将 $X$ 增加 $a_i$，否则将 $X$ 增加 $b_i$。
• $(s,t)$ 的美丽度为 $X$ 的最终值。

给出 $Q$ 个查询。按顺序处理这些查询。在第 $i$ 个查询中，将 $a_{p_i}$ 的值更新为 $x_i$，将 $b_{p_i}$ 的值更新为 $y_i$。然后，找到一个平衡括号序列对的最大可能的美丽度。

在这个问题中，只有以下序列被定义为平衡括号序列：

• 空字符串
• 按顺序连接 (、$s$、)，其中 $s$ 是一个平衡括号序列
• 按顺序连接 $s$、$t$，其中 $s$ 和 $t$ 是平衡括号序列

约束条件

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

输入

输入以以下格式从标准输入给出：

$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$ 个查询的响应。

示例输入 1

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

示例输出 1

15
15

• 第一个查询将 $a$ 和 $b$ 更新为 $a=(1,4,7,3)$，$b=(4,6,3,3)$。$(s,t)$=$($()()$,$()()$)$ 的最大可能美丽度为 $15$。
• 第二个查询将 $a$ 和 $b$ 更新为 $a=(1,4,2,3)$，$b=(4,6,5,3)$。$(s,t)$=$($()()$,$(())$)$ 的最大可能美丽度为 $15$。

示例输入 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

示例输出 2

311
312
260
286
296
292
327