Problem Description

Please note the special time limit of this problem.

Given a sequence $a$ of length $n$ and an integer $m$.

We define one operation as: simultaneously replace each element $a_i$ in sequence $a$ with the $\operatorname{mex}$ of all elements in sequence $a$ except $a_i$.

You need to output the sequence $a$ after performing $m$ operations.

Here, the $\operatorname{mex}$ of a sequence is the smallest natural number that does not appear in the sequence. For example:

• $\operatorname{mex}\{1,2,3\}=0$.
• $\operatorname{mex}\{0\}=1$.
• $\operatorname{mex}\{1,0,2,4\}=3$.
• $\operatorname{mex}\{2,1,3,0,2\}=4$.

In particular, when the sequence is empty, its $\operatorname{mex}$ is $0$.

Input Format

This problem has multiple test cases.

The first line contains an integer $T$, the number of test cases.

Then the test cases follow. For each test case:

• The first line contains two integers $n,m$.
• The second line contains $n$ integers, representing the given sequence $a$.

Output Format

For each test case, output one line containing $n$ integers separated by spaces, representing the sequence $a$ after performing $m$ operations.

3
4 1
1 0 1 2
4 5
9 9 6 1
3 5
1 3 0

3 0 3 2
0 0 0 0
1 2 0

Hint

"Sample Explanation #1"

For the first test case, since $\operatorname{mex}\{0,1,2\}=3$, $\operatorname{mex}\{1,1,2\}=0$, $\operatorname{mex}\{1,0,2\}=3$, and $\operatorname{mex}\{1,0,1\}=2$, the sequence $a$ after performing $1$ operation is $\{3,0,3,2\}$.

Constraints

Let $\sum n$ be the sum of $n$ within a single test point.

For all testdata, $1 \le T \le 1000$, $1 \le n \le 10^6$, $1 \le m \le 10^9$, $0 \le a_i \le 10^9$, and $\sum n \le 10^6$.

You can get the score for this problem only if you pass all test points.

Translated by ChatGPT 5