Tataramon

Jessie and James are hunting Tataramon, small creatures that live around the village. To capture one, they first have to fight it and then put it in a Tataraball.

The computer in their rocket predicted, in order, which Tataramon they will meet along their path. Every kind of Tataramon has its own number. For example, number 25 is called Pandan-kachu.

The two do not want to be greedy, so they take at most two Tataramon of each kind. At the same time, they want the sum of the numbers of every Tataramon they captured to be as large as possible.

Given the numbers of the Tataramon in the order they are encountered, pick each number at most twice so that the sum of the picked numbers is as large as possible. The captured Tataramon keep the order in which the two met them, so the answer is a subsequence of the original sequence.

The first line contains $T$, the number of test cases.

The first line of each test case contains an integer $N$. The second line contains $N$ integers $A_1, A_2, \dots, A_N$ separated by single spaces, the numbers of the Tataramon in the order Jessie and James meet them.

• $1 \le T \le 10$
• $1 \le N \le 100000$
• $1 \le A_i \le 10^9$

For each test case, print on one line the numbers $B_1, B_2, \dots, B_M$ of the Tataramon they should capture, separated by spaces. The numbers keep the order of the input, so $B_1, \dots, B_M$ is a subsequence of $A_1, \dots, A_N$.

Several subsequences can reach the maximum sum. In that case, print only the lexicographically smallest one. Every subsequence with the maximum sum has the same length, so compare two of them from the front: at the first position where they differ, the one with the smaller value comes first.