题目描述

Maddy 面前有 $n$ 条河豚鱼，每条河豚鱼有一个大小值 $a_i$，相差甚远的河豚鱼在一起会爆炸！因此 Maddy 选择了让它们排成一排。记排成一排之后从左到右河豚鱼的大小分别为 $a_1', a_2', \dots, a_n'$，则 Maddy 会称呼这排河豚鱼的爆炸度为

$$B = \sum \limits_{i < j, |i - j| > 1} |a_i' - a_j'|$$

现在河豚鱼在午夜发生了改变！具体而言共有 $m$ 次转变，每次转变会有一条河豚鱼 $id$ 的大小增加 $delt$ ($delt < 0$ 时为河豚鱼大小减小 $|delt|$)，在每次转变之后 Maddy 希望你能找到将河豚鱼排成一排的方法使得其爆炸度最小，你要求出此时的爆炸度 $B$。
注意每一次转变是具有后效性的，即前一次的转变效果会保留下来并影响后续的计算和转变。
注意河豚的大小可以是负数。

输入格式

第一行输入一个整数 $T$ ($1 \le T \le 10^5$)，表示数据组数。
每组测试数据输入的第一行输入两个整数 $n$ 和 $m$ ($2 \le n \le 10^5, 1 \le m \le 10^5$)，分别表示河豚鱼的个数和转变的次数。
随后一行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($-10^8 \le a_i \le 10^8$)，分别表示河豚鱼的大小，注意河豚鱼大小可以是负的。
随后 $m$ 行每行依次输入两个整数 $id$ 和 $delt$ ($1 \le id \le n, -10^8 \le delt \le 10^8$)，表示每次转变后的河豚鱼编号和河豚鱼大小变化值。
保证单组测试数据中，$\sum |delt| \le 10^8$，所有测试数据输入中所有的 $\sum n, \sum m \le 3 \times 10^5$。

输出格式

每组测试数据对于每次转变输出一行一个整数 $B$，表示转变之后使爆炸度最小的河豚鱼排列方法中的爆炸度。

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

3
6
8

提示

样例 1 解释

在第一次转变后河豚鱼的大小仍然为 $\{1, 2, 3, 4\}$，此时最优排列方法为 $\{2, 4, 1, 3\}$，爆炸度为 $B = |a_1 - a_3| + |a_1 - a_4| + |a_2 - a_4| = |2 - 1| + |2 - 3| + |4 - 3| = 3$。
在第二次转变后河豚鱼的大小为 $\{1, 7, 3, 4\}$，此时最优排列方法为 $\{3, 7, 1, 4\}$，爆炸度为 $B = |a_1 - a_3| + |a_1 - a_4| + |a_2 - a_4| = |3 - 1| + |3 - 4| + |7 - 4| = 6$。
在第三次转变后河豚鱼的大小为 $\{-1, 7, 3, 4\}$，此时最优排列方法为 $\{3, 7, -1, 4\}$，爆炸度为 $B = |a_1 - a_3| + |a_1 - a_4| + |a_2 - a_4| = |3 - (-1)| + |3 - 4| + |7 - 4| = 8$。