#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

Mex Extension - Repovive Premier Round 3 | Repovive

6E. Mex Extension

2500 pts2s256 MB

We define the score of an array $b_1,b_2,\ldots,b_m$ as follows.

Start with an empty set $S$ .

For each $i$ from $1$ to $m$ :

Insert $b_i$ into $S$ .
After that, you may insert $\operatorname{mex}(S)$ into $S$ .

The second step can be used at most $k$ times in total. Here $\operatorname{mex}(S)$ is the smallest non-negative integer that does not belong to $S$ .

The score of the array is the maximum possible value of $\operatorname{mex}(S)$ after all elements are processed.

You are given an array $a_1,a_2,\ldots,a_n$ . For each $r$ with $1 \le r \le n$ , output the score of the prefix $a_1,a_2,\ldots,a_r$ .

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le k \le n$
$0 \le a_i \le n$
The sum of $n$ over all test cases is at most $2 \times 10^5$

Input

t

\left. \begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} f(1) \quad f(2) \quad \cdots \quad f(n) \end{array} \right\} \times t

Here $f(r)$ is the score of the prefix $a_1,a_2,\ldots,a_r$ .

Samples

Input

Case 1

1 1
0

Case 2

4 1
1 0 3 2

Case 3

5 2
0 2 1 0 4

Case 4

6 3
3 3 0 1 2 6

Case 5

7 4
1 2 0 4 3 6 5

Explanation

Case 1

For the only prefix, we start with an empty set.

First, we insert $0$ , so $S=\{0\}$ . Then we use the operation and insert $\operatorname{mex}(S)=1$ . Now $S=\{0,1\}$ , so the final mex is $2$ .

Case 2

For the prefix $[1]$ , after inserting $1$ , we use the operation and insert $0$ . The final set contains $0$ and $1$ , so the score is $2$ .

For the prefix $[1,0]$ , first insert $1$ , then use the operation to insert $0$ . After that, the array also inserts $0$ . The final set contains $0$ and $1$ , so the score is $2$ .

For the prefix $[1,0,3]$ , first insert $1$ , then insert $0$ . After that, use the operation and insert $2$ . Finally, insert $3$ . The final set contains $0,1,2,3$ , so the score is $4$ .

For the prefix $[1,0,3,2]$ , the same operation after inserting $0$ gives $2$ . The final set contains $0,1,2,3$ , so the score is $4$ .

Case 3

For the full prefix $[0,2,1,0,4]$ , use the first operation after inserting $0$ to insert $1$ . Then insert $2$ from the array. Use the second operation to insert $3$ . Finally, the array inserts $4$ . The final set contains $0,1,2,3,4$ , so the score is $5$ .

Case 4

For the prefix $[3,3,0]$ , after inserting the first $3$ , use one operation to insert $0$ . After inserting the second $3$ , use another operation to insert $1$ . After inserting $0$ , use the last operation to insert $2$ . The final set contains $0,1,2,3$ , so the score is $4$ .

Case 5

For the full prefix $[1,2,0,4,3,6,5]$ , use the operations after inserting the 3rd, 4th, 6th, and 7th elements.

After inserting $0$ , the set contains $0,1,2$ , so the operation inserts $3$ .

After inserting $4$ , the operation inserts $5$ .

After inserting $6$ , the operation inserts $7$ .

After inserting $5$ , the operation inserts $8$ .

So the final set contains all numbers from $0$ to $8$ , and the score is $9$ .

Output

Case 1

Case 2

2 3 4 5

Case 3

2 4 4 5 6

Case 4

1 2 4 4 5 7

Case 5

2 4 5 6 7 8 9

We define the score of an array $b_1,b_2,\ldots,b_m$ as follows.

Start with an empty set $S$ .

For each $i$ from $1$ to $m$ :

Insert $b_i$ into $S$ .
After that, you may insert $\operatorname{mex}(S)$ into $S$ .

The second step can be used at most $k$ times in total. Here $\operatorname{mex}(S)$ is the smallest non-negative integer that does not belong to $S$ .

The score of the array is the maximum possible value of $\operatorname{mex}(S)$ after all elements are processed.

You are given an array $a_1,a_2,\ldots,a_n$ . For each $r$ with $1 \le r \le n$ , output the score of the prefix $a_1,a_2,\ldots,a_r$ .

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le k \le n$
$0 \le a_i \le n$
The sum of $n$ over all test cases is at most $2 \times 10^5$

t

\left. \begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

\left. \begin{array}{l} f(1) \quad f(2) \quad \cdots \quad f(n) \end{array} \right\} \times t

Here $f(r)$ is the score of the prefix $a_1,a_2,\ldots,a_r$ .

For the only prefix, we start with an empty set.

First, we insert $0$ , so $S=\{0\}$ . Then we use the operation and insert $\operatorname{mex}(S)=1$ . Now $S=\{0,1\}$ , so the final mex is $2$ .

For the prefix $[1]$ , after inserting $1$ , we use the operation and insert $0$ . The final set contains $0$ and $1$ , so the score is $2$ .

For the prefix $[1,0]$ , first insert $1$ , then use the operation to insert $0$ . After that, the array also inserts $0$ . The final set contains $0$ and $1$ , so the score is $2$ .

For the prefix $[1,0,3]$ , first insert $1$ , then insert $0$ . After that, use the operation and insert $2$ . Finally, insert $3$ . The final set contains $0,1,2,3$ , so the score is $4$ .

For the prefix $[1,0,3,2]$ , the same operation after inserting $0$ gives $2$ . The final set contains $0,1,2,3$ , so the score is $4$ .

For the full prefix $[1,2,0,4,3,6,5]$ , use the operations after inserting the 3rd, 4th, 6th, and 7th elements.

After inserting $0$ , the set contains $0,1,2$ , so the operation inserts $3$ .

After inserting $4$ , the operation inserts $5$ .

After inserting $6$ , the operation inserts $7$ .

After inserting $5$ , the operation inserts $8$ .

So the final set contains all numbers from $0$ to $8$ , and the score is $9$ .

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

6E. Mex Extension

Constraints

Input

Output

Samples

6E. Mex Extension

Constraints

Input

Output

Samples