Problem Description

There are $n$ pufferfish in front of Maddy. Each pufferfish has a size value $a_i$. Pufferfish with very different sizes will explode when placed together, so Maddy decides to arrange them in a line. Let the sizes from left to right after arranging be $a_1', a_2', \dots, a_n'$. Then Maddy defines the explosion level of this line of pufferfish as

Now the pufferfish change at midnight. Specifically, there are $m$ transformations. In each transformation, the size of one pufferfish $id$ increases by $delt$ (when $delt < 0$, the pufferfish size decreases by $|delt|$). After each transformation, Maddy wants you to find an arrangement of the pufferfish in a line that minimizes the explosion level, and you need to output the corresponding explosion level $B$.
Note that each transformation has a lasting effect, meaning the effect of the previous transformation remains and will affect subsequent computations and transformations.
Also note that pufferfish sizes can be negative.

Input Format

The first line contains an integer $T$ ($1 \le T \le 10^5$), indicating the number of test cases.
For each test case, the first line contains two integers $n$ and $m$ ($2 \le n \le 10^5, 1 \le m \le 10^5$), representing the number of pufferfish and the number of transformations.
The next line contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^8 \le a_i \le 10^8$), representing the sizes of the pufferfish. Note that pufferfish sizes can be negative.
Then follow $m$ lines, each containing two integers $id$ and $delt$ ($1 \le id \le n, -10^8 \le delt \le 10^8$), indicating the index of the pufferfish and the change in its size for each transformation.
It is guaranteed that for each test case, $\sum |delt| \le 10^8$, and over all input testdata, $\sum n$ and $\sum m$ are both at most $3 \times 10^5$.

Output Format

For each test case, output one integer $B$ per line for each transformation, representing the minimum possible explosion level among all arrangements after that transformation.

1
4 3
1 2 3 4
4 0
2 5
1 -2

3
6
8

Hint

Sample 1 Explanation

After the first transformation, the pufferfish sizes are still $\{1, 2, 3, 4\}$. The optimal arrangement is $\{2, 4, 1, 3\}$, and the explosion level is $B = |a_1 - a_3| + |a_1 - a_4| + |a_2 - a_4| = |2 - 1| + |2 - 3| + |4 - 3| = 3$。
After the second transformation, the pufferfish sizes are $\{1, 7, 3, 4\}$. The optimal arrangement is $\{3, 7, 1, 4\}$, and the explosion level is $B = |a_1 - a_3| + |a_1 - a_4| + |a_2 - a_4| = |3 - 1| + |3 - 4| + |7 - 4| = 6$。
After the third transformation, the pufferfish sizes are $\{-1, 7, 3, 4\}$. The optimal arrangement is $\{3, 7, -1, 4\}$, and the explosion level is $B = |a_1 - a_3| + |a_1 - a_4| + |a_2 - a_4| = |3 - (-1)| + |3 - 4| + |7 - 4| = 8$。

Translated by ChatGPT 5