Toxel 喜欢数组。在前往帕尔迪亚地区之前,薮猫送给他一个阵列$$$a$$$作为礼物。该数组具有 $$$n$$$ 成对不同的元素。
为了获得更多数组,Toxel 对初始数组执行了 $$$m$$$ 操作。在第$$$i$$$操作中,他将第$$$(i-1)$$$数组的第$$$p_{i}$$$元素修改为$$$v_{i}$$$,得到第$$$i$$$数组(初始数组$$$a$$$编号为$$$0$$$)。在修改过程中,Toxel 保证每个数组的元素在每次操作后仍然成对不同。
最后,Toxel 得到了 $$$m+1$$$ 数组,并将它们表示为 $$$A_{0}=a, A_{1},\ldots,A_{m}$$$。对于每对 $$$(i,j)$$$ ($$$0\le i<j\le m$$$),Toxel 将其值定义为 $$$A_{i}$$$ 和 $$$A_{j}$$$ 连接的不同元素的数量。现在托克塞尔想知道,所有对的值的总和是多少?请帮他算出答案。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量$$$t$$$ ($$$1\le t\le10^{4}$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1\le n,m\le2\cdot10^{5}$$$) — 数组的长度和操作数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_{1},a_{2},\dots,a_{n}$$$ ($$$1\le a_{i}\le n+m$$$)。保证所有 $$$a_i$$$ 都是成对不同的。
每个测试用例接下来的 $$$m$$$ 行都包含两个整数 $$$p_{i}$$$ 和 $$$v_{i}$$$ ($$$1\le p_{i}\le n$$$, $$$1\le v_{i}\le n+m$$$) — 修改元素的位置及其新值。确保每次修改后每个数组的元素仍然成对不同。
保证所有测试用例的 $$$n$$$ 之和与 $$$m$$$ 之和不超过 $$$2\cdot10^{5}$$$。
输出
对于每个测试用例,打印一个整数 - 所有数组对的值的总和。
示例
输入 #1
3 3 2 1 2 3 1 4 2 5 1 1 1 1 1 10 10 4 6 9 12 16 20 2 10 19 7 1 3 5 4 2 17 2 18 6 11 7 1 8 17 5 5 5 5 2 2
输出 #1
13 1 705
注意
在第一个测试用例中,数组更改如下:$$$[1,2,3]\to[\underline{4},2,3]\to[4,\underline{5},3]$$$。
第 $$$0$$$ 个数组和第 $$$1$$$ 个数组的串联为 $$$\require{cancel}[1,2,3,4,\cancel{2},\cancel{3}]$$$。有 $$$4$$$ 不同的元素。
第 $$$0$$$ 个数组和第 $$$2$$$ 个数组的串联是 $$$\require{cancel}[1,2,3,4,5,\cancel{3}]$$$。有 $$$5$$$ 不同的元素。
$$$1$$$-st 数组和 $$$2$$$-nd 数组的串联是 $$$\require{cancel}[4,2,3,\cancel{4},5,\cancel{3}]$$$。有 $$$4$$$ 不同的元素。
删除线元素在数组中是重复的。
因此,答案是$$$4+5+4=13$$$。
在第二个测试用例中,请注意,数组在操作后可能保持不变。