Дан массив \(a_1,a_2,\ldots, a_n\), состоящий из попарно различных целых чисел от \(0\) до \(n\). Рассмотрим следующую операцию:
- последовательно для каждого \(i\) от \(1\) до \(n\) в этом порядке элемент \(a_i\) заменяется на \(\operatorname{MEX}(a_1, a_2, \ldots, a_n)\).
Здесь \(\operatorname{MEX}\) набора чисел \(c_1, c_2, \ldots, c_m\) определяется как наименьшее неотрицательное целое число \(x\), которое не встречается в наборе чисел \(c\). Например, \(\operatorname{MEX}(0, 2, 2, 1, 4) = 3\), и \(\operatorname{MEX}(1, 2) = 0\).
Выведите массив, который получится после применения к нему такой операции \(k\) раз.
Выходные данные
Для каждого набора входных данных выведите все \(n\) элементов итогового массива после применения к нему операции \(k\) раз.
Примечание
В первом наборе входных данных процесс происходит следующим образом:
- На первой операции массив изменяется с \([1]\) на \([0]\), поскольку \(\operatorname{MEX}(1) = 0\).
- На второй операции массив изменяется с \([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]\).
Примеры
| № | Входные данные | Выходные данные |
|
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
2 0 1
2 1
2 3 4 5 0
7 5 3 0 4 2 1 6 9 10
|