C. Carrot Party
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Busy Beaver and Sneaky Snake visit a carrot shop. There are $$$N$$$ carrots for sale, arranged in a row from left to right. The carrots are numbered $$$1, 2, \dots, N$$$ from left to right, and the $$$i$$$-th carrot has a flavor index $$$a_i$$$.

They want to eat carrots to maximize their total satisfaction. They take turns eating carrots, with Busy Beaver going first.

  • On Busy Beaver's turn, he eats one of the two leftmost remaining carrots.
  • On Sneaky Snake's turn, she eats one of the two rightmost remaining carrots.
  • If only one carrot remains, the player whose turn it is must eat it.

When a player eats a carrot, they gain satisfaction equal to that carrot's flavor index. The game ends when all carrots have been eaten.

Both players play optimally to maximize their own total satisfaction. Before they start, Busy Beaver wants to know the final total satisfactions of Busy Beaver and Sneaky Snake.

Furthermore, the shop owner frequently changes the flavor index of a carrot. There are $$$Q$$$ modifications; in each modification, the flavor index of one carrot is changed. After each modification, compute the final total satisfactions of both players. Note that the modifications are applied cumulatively.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$N$$$ and $$$Q$$$ ($$$4 \le N \le 2 \cdot 10^5$$$, $$$0 \le Q \le 2 \cdot 10^5$$$).

The second line of each test case contains $$$N$$$ integers $$$a_1, a_2, \dots, a_N$$$, where $$$a_i$$$ is the initial flavor index of the $$$i$$$-th carrot ($$$1 \le a_i \le 10^9$$$).

Each of the next $$$Q$$$ lines contains two integers $$$x_i$$$ and $$$v_i$$$, meaning that in the $$$i$$$-th modification, the flavor index of the $$$x_i$$$-th carrot is changed to $$$v_i$$$ ($$$1 \le x_i \le N$$$, $$$1 \le v_i \le 10^9$$$).

The sum of $$$N$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

The sum of $$$Q$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output $$$Q+1$$$ lines.

On the first line, output the final total satisfactions of Busy Beaver and Sneaky Snake respectively for the initial flavor indices.

On the next $$$Q$$$ lines, in the $$$i$$$-th line, output the final total satisfactions after applying the first $$$i$$$ modifications.

Scoring

There are three subtasks for this problem.

  • ($$$10$$$ points): $$$N = 4$$$.
  • ($$$30$$$ points): $$$Q = 0$$$.
  • ($$$60$$$ points): No additional constraints.
Example
Input
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
Output
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
Note

In the first test case, the initial flavor indices are $$$A = [3, 5, 1, 6]$$$. The game will proceed as follows.

  1. Busy Beaver can take either the first or the second carrot. He takes the second carrot and gains $$$5$$$ satisfaction.
  2. Sneaky Snake can take either the third or the fourth carrot. She takes the fourth carrot and gains $$$6$$$ satisfaction.
  3. Busy Beaver can take either the first or the third carrot. He takes the first carrot and gains $$$3$$$ satisfaction.
  4. Sneaky Snake can only take the third carrot. She gains $$$1$$$ satisfaction.

At the end of the game, Busy Beaver has total satisfaction $$$8$$$, and Sneaky Snake has total satisfaction $$$7$$$.