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

Мода массива — это число, которое имеет максимальное количество вхождений в массиве. Если несколько чисел имеют максимальное количество вхождений, модой является максимальное по значению из них. Например, мода массива $$$[1, 1, 2]$$$ это $$$1$$$, а мода массива $$$[3, 4]$$$ это $$$4$$$.

Вам дан массив $$$a$$$, состоящий из $$$n$$$ целых чисел. Вы можете произвольно переставлять числа в массиве $$$a$$$ в любом порядке. Ваша задача — переставить числа в массиве $$$a$$$ таким образом, чтобы сумма мод по всем префиксам массива была максимальна.

Например, массив $$$[2, 3, 2]$$$ можно переставить как $$$[3, 2, 2]$$$. Тогда сумма мод по всем префиксам определяется следующим образом:

  • Префикс длины $$$1$$$ это $$$[3]$$$. Мода этого префикса равна $$$3$$$.
  • Префикс длины $$$2$$$ это $$$[3, 2]$$$. Мода этого префикса равна $$$3$$$.
  • Префикс длины $$$3$$$ это $$$[3, 2, 2]$$$. Мода этого префикса равна $$$2$$$.
Таким образом, сумма мод равна $$$3 + 3 + 2 = 8$$$. Можно доказать, что при такой расстановке массива $$$a$$$ ответ является максимальным.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — размер массива.

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

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

Для каждого набора входных данных выведите новый массив, у которого сумма мод по всем префиксам максимальна. Если оптимальных ответов несколько, выведите любой из них.

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

Первый набор входных данных описывается в условиях задачи.

Во втором наборе входных данных одной из подходящих расстановок является $$$[4, 4, 3, 2, 1, 1]$$$. Мода на каждом из префиксов равна $$$4$$$.

В третьем наборе входных данных расстановка $$$[4, 1, 3, 2, 2]$$$ подходит как ответ. Мода на каждом префиксе:

  • Префикс длины $$$1$$$ это $$$[4]$$$. Мода этого префикса равна $$$4$$$.
  • Префикс длины $$$2$$$ это $$$[4, 1]$$$. Мода этого префикса равна $$$4$$$.
  • Префикс длины $$$3$$$ это $$$[4, 1, 3]$$$. Мода этого префикса равна $$$4$$$.
  • Префикс длины $$$4$$$ это $$$[4, 1, 3, 2]$$$. Мода этого префикса равна $$$4$$$.
  • Префикс длины $$$5$$$ это $$$[4, 1, 3, 2, 2]$$$. Мода этого префикса равна $$$2$$$.
Тогда сумма мод равна $$$4 + 4 + 4 + 4 + 2 = 18$$$. Можно доказать, что данная расстановка максимизирует сумму мод.