← 返回题目列表

Codeforces · 1863/C

C. MEX 重复

中文机器翻译题面 查看原题

给定一个数组 $$$a_1,a_2,\ldots, a_n$$$,其中包含从 $$$0$$$ 到 $$$n$$$ 的成对不同整数。考虑以下操作:

- 对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,按此顺序连续将 $$$a_i$$$ 替换为 $$$\operatorname{MEX}(a_1, a_2, \ldots, a_n)$$$。

这里 $$$\operatorname{MEX}$$$ 的整数集合 $$$c_1, c_2, \ldots, c_m$$$ 被定义为集合 $$$c$$$ 中不出现的最小非负整数 $$$x$$$。例如,$$$\operatorname{MEX}(0, 2, 2, 1, 4) = 3$$$ 和 $$$\operatorname{MEX}(1, 2) = 0$$$。

应用 $$$k$$$ 这样的操作后打印数组。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1\le n\le 10^5$$$, $$$1\le k\le 10^9$$$)。

第二行包含 $$$n$$$ 成对不同的整数 $$$a_1,a_2,\ldots, a_n$$$ ($$$0\le a_i\le n$$$) 表示应用操作之前数组的元素。

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

输出

对于每个测试用例,在应用 $$$k$$$ 操作后打印数组的所有 $$$n$$$ 元素。

示例

输入 #1

5
1 2
1
3 1
0 1 3
2 2
0 2
5 5
1 2 3 4 5
10 100
5 3 0 4 2 1 6 9 10 8

输出 #1

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

注意

在第一个测试用例中,以下是整个过程:

1. 在第一个操作中,数组从 $$$[1]$$$ 更改为 $$$[0]$$$,因为 $$$\operatorname{MEX}(1) = 0$$$。
2. 在第二个操作中,数组从 $$$[0]$$$ 更改为 $$$[1]$$$,因为 $$$\operatorname{MEX}(0) = 1$$$。

因此,经过两次操作后,数组就变成了$$$[1]$$$。

在第二个测试用例中,数组在一次操作期间发生如下变化: $$$[{\mkern3mu\underline{\mkern-3mu {\bf 0}\mkern-3mu}\mkern3mu}, 1, 3] \rightarrow [2, {\mkern3mu\underline{\mkern-3mu {\bf 1}\mkern-3mu}\mkern3mu}, 3] \rightarrow [2, 0, {\mkern3mu\underline{\mkern-3mu {\bf 3}\mkern-3mu}\mkern3mu}] \rightarrow [2, 0, 1]$$$。

在第三个测试用例中,数组在一次操作期间发生如下变化: $$$[{\mkern3mu\underline{\mkern-3mu {\bf 0}\mkern-3mu}\mkern3mu}, 2] \rightarrow [1, {\mkern3mu\underline{\mkern-3mu {\bf 2}\mkern-3mu}\mkern3mu}] \rightarrow [1, 0]$$$。在第二次操作期间: $$$[{\mkern3mu\underline{\mkern-3mu {\bf 1}\mkern-3mu}\mkern3mu}, 0] \rightarrow [2, {\mkern3mu\underline{\mkern-3mu {\bf 0}\mkern-3mu}\mkern3mu}] \rightarrow [2, 1]$$$。