A. Мексимизация
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано число $$$n$$$ и массив $$$a_1, a_2, \ldots, a_n$$$. Необходимо переставить числа в массиве $$$a$$$ так, чтобы сумма $$$\textbf{MEX}$$$ на всех префиксах массива ($$$i$$$-й префикс  — это $$$a_1, a_2, \ldots, a_i$$$) была максимальна.

Формально, вам нужно найти массив $$$b_1, b_2, \ldots, b_n$$$, такой что наборы чисел массивов $$$a$$$ и $$$b$$$ совпадают (то есть массив $$$b$$$ получается некоторой перестановкой чисел в массиве $$$a$$$) и $$$\sum\limits_{i=1}^{n} \textbf{MEX}(b_1, b_2, \ldots, b_i)$$$ максимальна.

Напомним, что $$$\textbf{MEX}$$$ множества целых неотрицательных чисел  — такое минимальное целое неотрицательное число, которое не входит в это множество.

Например, $$$\textbf{MEX}(\{1, 2, 3\}) = 0$$$, $$$\textbf{MEX}(\{0, 1, 2, 4, 5\}) = 3$$$.

Входные данные

В первой строке находится единственное целое число $$$t$$$ $$$(1 \le t \le 100)$$$  — количество наборов входных данных.

В первой строке описания каждого набора входных данных находится единственное целое число $$$n$$$ $$$(1 \le n \le 100)$$$.

Во второй строке описания каждого набора входных данных находится $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ $$$(0 \le a_i \le 100)$$$.

Выходные данные

Для каждого набора входных данных выведите массив $$$b_1, b_2, \ldots, b_n$$$, являющийся оптимальной перестановкой чисел $$$a_1, a_2, \ldots, a_n$$$, то есть сумма $$$\textbf{MEX}$$$ на всех его префиксах максимальна.

Если существует несколько оптимальных ответов, вы можете найти любой.

Пример
Входные данные
3
7
4 2 0 1 3 3 7
5
2 2 8 6 9
1
0
Выходные данные
0 1 2 3 4 7 3 
2 6 8 9 2 
0 
Примечание

В первом наборе входных данных в ответе $$$\textbf{MEX}$$$ на префиксах будет таким:

  1. $$$\textbf{MEX}(\{0\}) = 1$$$
  2. $$$\textbf{MEX}(\{0, 1\}) = 2$$$
  3. $$$\textbf{MEX}(\{0, 1, 2\}) = 3$$$
  4. $$$\textbf{MEX}(\{0, 1, 2, 3\}) = 4$$$
  5. $$$\textbf{MEX}(\{0, 1, 2, 3, 4\}) = 5$$$
  6. $$$\textbf{MEX}(\{0, 1, 2, 3, 4, 7\}) = 5$$$
  7. $$$\textbf{MEX}(\{0, 1, 2, 3, 4, 7, 3\}) = 5$$$
Сумма $$$\textbf{MEX} = 1 + 2 + 3 + 4 + 5 + 5 + 5 = 25$$$. Можно показать, что это максимальная возможная сумма $$$\textbf{MEX}$$$ на префиксах.