CF2137E.Mexification

You are given an array $a$ of size $n$ and an integer $k$. You do the following procedure $k$ times:

• For each element $a_i$, you set $a_i$ to $\operatorname{mex}$$^{\text{∗}}$$(a_1,a_2,\ldots,a_{i-1},a_{i+1},a_{i+2}, \ldots,a_n)$. In other words, you set $a_i$ to the $\operatorname{mex}$ of all other elements in the array. This is done for all elements in the array at the same time.

Please find the sum of elements in the array after all $k$ operations.

$^{\text{∗}}$The minimum excluded (MEX) of a collection of integers $d_1, d_2, \ldots, d_k$ is defined as the smallest non-negative integer $x$ which does not occur in the collection $d$.

给你一个大小为 $n$ 的数组 $a$ 和一个整数 $k$。你执行以下操作 $k$ 次：

• 对于每个元素 $a_i$，将其设置为 $\operatorname{mex}$$^{\text{∗}}$$(a_1,a_2,\ldots,a_{i-1},a_{i+1},a_{i+2}, \ldots,a_n)$。换言之，将 $a_i$ 设置为数组中其余所有元素的 $\operatorname{mex}$。该操作对数组中所有元素同时进行。

请计算经过全部 $k$ 次操作后，数组中所有元素的和。

$^{\text{∗}}$ 一组整数 $d_1, d_2, \ldots, d_k$ 的最小未出现值（MEX） 定义为未在该集合 $d$ 中出现的最小非负整数 $x$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line contains two integers $n$ and $k$ ($2 \leq n \leq 2\cdot 10^5, 1 \leq k \leq 10^9$) – the number of elements in $a$ and the number of operations done.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0 \leq a_i \leq n$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 2\cdot 10^5,\ 1 \leq k \leq 10^9$）——分别表示数组 $a$ 的元素个数以及执行的操作次数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0 \leq a_i \leq n$）。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

For each test case, output the sum of elements after all $k$ operations on a new line.

对于每个测试用例，在一行中输出执行所有 $k$ 次操作后的元素之和。

In the first test case, we performed the operation on the array $[0,2,1]$ three times. Let's compute the result after the first time:

• The first element becomes $\operatorname{MEX}(2,1)=0$
• The second element becomes $\operatorname{MEX}(0,1)=2$
• The third element becomes $\operatorname{MEX}(0,2)=1$

So, after the first operation, $[0,2,1]$ becomes $[0,2,1]$ again. It can be shown that the array will not change no matter how many times we perform the operation, so the final array after three operations is still $[0,2,1]$. The sum is $0+2+1=3$.

In the third test case, the array becomes $[2,2,2,2]$.

在第一个测试用例中，我们对数组 $[0,2,1]$ 执行了三次操作。我们来计算第一次操作后的结果：

• 第一个元素变为 $\operatorname{MEX}(2,1)=0$；
• 第二个元素变为 $\operatorname{MEX}(0,1)=2$；
• 第三个元素变为 $\operatorname{MEX}(0,2)=1$。

因此，第一次操作后，$[0,2,1]$ 仍为 $[0,2,1]$。可以证明，无论执行多少次该操作，数组均不会发生变化，故经过三次操作后的最终数组仍是 $[0,2,1]$。其元素和为 $0+2+1=3$。

在第三个测试用例中，数组变为 $[2,2,2,2]$。