小 $E$ 决定在小 $L$ 生日时送她一个项链，用来展现自己的诚心，这个项链将从一个已有的项链中提纯得到。

具体的，项链由 $n$ 个宝珠构成，每个宝珠有价值 $a_i$。

小 $E$ 可以选择其中若干宝珠，目标是最大化得到的宝珠价值之和，但要满足不能选择连续的 $>3$ 个宝珠，注意项链是环形的，所以首尾交接处也要满足这个规则。

情报可能有误，所以有若干修改操作 $x\ v$，表示将 $a_x$ 修改为 $v$。

请在初始情况，以及每次修改后，回答小 $L$ 能得到的宝珠最大价值和。

输入格式

本题有多组测试数据。第一行一个正整数 $T$，表示数据组数，接下来输入每组测试数据。

对于每组测试数据：

第一行两个正整数 $n,q$，表示项链长度和修改次数。

第二行 $n$ 个正整数，表示价值序列 $a_1,a_2,\dots,a_n$。

接下来 $q$ 行，每行两个正整数 $x,v$，表示一次修改操作。

输出格式

对于初始情况以及每次修改，输出一行一个整数，表示对应的答案。

样例

输入

1
5 3
1 2 3 4 5
1 5
5 1
3 1

输出

12
14
12
11

提示

对于所有数据，$1\leq T\leq 5,4\leq n\leq 2\times 10^5,1\leq q\leq 10^5$，$1\leq a_i,v\leq 10^9$。