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$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

6E. Mex Extension

Constraints

Input

Output

Samples

6E. Mex Extension

Constraints

Input

Output

Samples