No testdata at current.

[T4] 覆盖

题目描述

对于一个长为 $m$ 的序列 $b_1,b_2,\dots,b_m$，如果某个数 $x$ 在这个序列中出现的次数严格大于 $\frac{m}{2}$，那么称 $x$ 是这个序列的主元。

现在给定一个长为 $n$ 的序列 $a_1,a_2,\dots,a_n$。

每次操作，你可以选择一个存在主元的子段 $a_l,a_{l+1},\dots,a_r$。结合公开检索片段与样例可确定，这里的“覆盖”操作含义为：

• 将这个子段中的所有元素，全部修改为该子段的主元。

你可以执行任意多次这样的操作。请你求出，最终能够得到的字典序最小的序列。

输入格式

从标准输入按以下格式读取数据：

$T$

$n$

$a_1$ $a_2$ $\dots$ $a_n$

其中：

• 第一行输入一个正整数 $T$，表示数据组数。
• 对于每组数据：
  • 第一行输入一个正整数 $n$，表示序列长度；
  • 第二行输入 $n$ 个整数，表示序列 $a_1,a_2,\dots,a_n$。

输出格式

对于每组数据，输出一行 $n$ 个整数，表示可以获得的字典序最小的序列。

数据范围

根据公开检索片段可确认：

• 对于 $30\%$ 的数据，$1 \le T \le 10$，$1 \le n \le 20$
• 对于另外 $30\%$ 的数据，$a_i \le 2$

完整的 $100\%$ 数据范围在公开检索片段中未完整显示。

样例

3
4
2 1 1 2
6
3 4 1 3 2 6
7
4 3 3 4 3 2 5

1 1 1 1
3 4 1 3 2 6
3 3 3 3 3 2 5