Busy Beaver 和 Sneaky Snake 来到一家胡萝卜店。店里有 $N$ 个胡萝卜待售，从左到右排成一排。胡萝卜从左到右编号为 $1, 2, \dots, N$，第 $i$ 个胡萝卜的美味指数为 $a_i$。

他们想要通过吃胡萝卜来最大化各自的总满意度。他们轮流吃胡萝卜，Busy Beaver 先手。

• 在 Busy Beaver 的回合，他吃掉当前剩余胡萝卜中最左侧的两个胡萝卜中的任意一个。
• 在 Sneaky Snake 的回合，她吃掉当前剩余胡萝卜中最右侧的两个胡萝卜中的任意一个。
• 如果只剩下一个胡萝卜，当前轮到谁，谁就必须吃掉它。

当玩家吃掉一个胡萝卜时，他们获得的满意度等于该胡萝卜的美味指数。当所有胡萝卜都被吃完时，游戏结束。

双方都采取最优策略以最大化各自的总满意度。在开始之前，Busy Beaver 想知道他和 Sneaky Snake 最终的总满意度分别是多少。

此外，店主经常会改变某个胡萝卜的美味指数。共有 $Q$ 次修改；每次修改都会改变一个胡萝卜的美味指数。在每次修改后，计算双方最终的总满意度。注意，修改是累积生效的。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。

每个测试用例的第一行包含两个整数 $N$ 和 $Q$ ($4 \le N \le 2 \cdot 10^5, 0 \le Q \le 2 \cdot 10^5$)。

每个测试用例的第二行包含 $N$ 个整数 $a_1, a_2, \dots, a_N$，其中 $a_i$ 是第 $i$ 个胡萝卜的初始美味指数 ($1 \le a_i \le 10^9$)。

接下来的 $Q$ 行，每行包含两个整数 $x_i$ 和 $v_i$，表示在第 $i$ 次修改中，第 $x_i$ 个胡萝卜的美味指数变为 $v_i$ ($1 \le x_i \le N, 1 \le v_i \le 10^9$)。

所有测试用例的 $N$ 之和不超过 $2 \cdot 10^5$。 所有测试用例的 $Q$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出 $Q + 1$ 行。

第一行输出初始美味指数下 Busy Beaver 和 Sneaky Snake 的最终总满意度。

接下来的 $Q$ 行，第 $i$ 行输出应用前 $i$ 次修改后的最终总满意度。

子任务

本题共有三个子任务：

• (10 分)：$N = 4$。
• (30 分)：$Q = 0$。
• (60 分)：无附加限制。

样例

输入 1

4
4 0
3 5 1 6
4 6
2 7 4 1
2 5
1 6
3 9
2 2
4 11
3 1
9 0
4 2 3 7 5 1 6 9 8
8 5
4 3 6 5 10 1 2 7
2 8
5 4
6 9
3 3
2 15

输出 1

8 7
9 5
7 5
11 5
11 10
8 10
15 13
8 12
20 25
18 20
23 20
23 14
23 22
20 22
27 22

说明

在第一个测试用例中，初始美味指数为 $A = [3, 5, 1, 6]$。游戏过程如下：

1. Busy Beaver 可以选择第一个或第二个胡萝卜。他选择了第二个胡萝卜，获得了 5 点满意度。
2. Sneaky Snake 可以选择第三个或第四个胡萝卜。她选择了第四个胡萝卜，获得了 6 点满意度。
3. Busy Beaver 可以选择第一个或第三个胡萝卜。他选择了第一个胡萝卜，获得了 3 点满意度。
4. Sneaky Snake 只能选择第三个胡萝卜。她获得了 1 点满意度。

游戏结束时，Busy Beaver 的总满意度为 8，Sneaky Snake 的总满意度为 7。