CF2267B.Fashionable Array

The mode of an array — is the number that appears the maximum number of times in the array. If several numbers appear the maximum number of times, the mode is the largest among them. For example, the mode of the array $[1, 1, 2]$ is $1$, and the mode of the array $[3, 4]$ is $4$.

You are given an array $a$ consisting of $n$ integers. You may arbitrarily permute the numbers in array $a$ in any order. Your task — is to rearrange the numbers in array $a$ so that the sum of the modes over all prefixes of the array is maximized.

For example, the array $[2, 3, 2]$ can be rearranged as $[3, 2, 2]$. Then the sum of the modes over all prefixes is determined as follows:

• The prefix of length $1$ is $[3]$. The mode of this prefix is $3$.
• The prefix of length $2$ is $[3, 2]$. The mode of this prefix is $3$.
• The prefix of length $3$ is $[3, 2, 2]$. The mode of this prefix is $2$.

Thus, the sum of the modes is $3 + 3 + 2 = 8$. It can be proven that for this arrangement of array $a$, the answer is maximal.

数组的众数是指在数组中出现次数最多的数。如果存在多个出现次数最多的数，则众数为其中最大的那个数。例如，数组 $[1, 1, 2]$ 的众数是 $1$，而数组 $[3, 4]$ 的众数是 $4$。

给定一个由 $n$ 个整数组成的数组 $a$。你可以以任意顺序重新排列（即置换）数组 $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$ 的这种排列方式，所得答案为最大值。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.

The first line of each test case contains one integer $n$ ($1 \le n \le 100$) — the size of the array.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots a_n$ ($1 \le a_i \le 100$) — the elements of the array.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$）—— 数组的元素。

For each test case, output a new array whose sum of the modes over all prefixes is maximal. If there are several optimal answers, output any of them.

对于每个测试用例，输出一个新数组，使得该数组所有前缀的众数之和最大。如果存在多个最优解，输出其中任意一个即可。

The first test case is described in the statement of the problem.

In the second test case, one suitable arrangement is $[4, 4, 3, 2, 1, 1]$. The mode of each prefix is $4$.

In the third test case, the arrangement $[4, 1, 3, 2, 2]$ is a valid answer. The mode of each prefix:

• The prefix of length $1$ is $[4]$. The mode of this prefix is $4$.
• The prefix of length $2$ is $[4, 1]$. The mode of this prefix is $4$.
• The prefix of length $3$ is $[4, 1, 3]$. The mode of this prefix is $4$.
• The prefix of length $4$ is $[4, 1, 3, 2]$. The mode of this prefix is $4$.
• The prefix of length $5$ is $[4, 1, 3, 2, 2]$. The mode of this prefix is $2$.

Then the sum of the modes is $4 + 4 + 4 + 4 + 2 = 18$. It can be proven that this arrangement maximizes the sum of the modes.

第一个测试用例已在题目描述中给出。

在第二个测试用例中，一种可行的排列是 $[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$。可以证明该排列使得众数之和达到最大。