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

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

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

The $\operatorname{mex}$ of a sequence is the smallest non-negative integer not present 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$.

Specifically, when a sequence is empty, its $\operatorname{mex}$ is $0$.

Input

This problem contains multiple test cases.

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

The following lines contain the test cases. For each test case:

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

Output

For each test case, output a single line containing $n$ space-separated integers, representing the sequence $a$ after performing $m$ operations.

Examples

Input 1

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

Output 1

3 0 3 2
0 0 0 0
1 2 0

Note 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 $1$ operation is $\{3,0,3,2\}$.

Constraints

Let $\sum n$ denote the sum of $n$ over all test cases.

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