A. Beautiful Bracelets
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Busy Beaver has collected some pairs of seashells, and he is trying to make them into two beautiful bracelets!

He has $$$N$$$ pairs of seashells, where both seashells in the $$$i$$$-th pair have type $$$a_i$$$. He wants to make two bracelets, such that each bracelet has one seashell from each pair. Busy Beaver decides his own metric for a beautiful pair of bracelets, which is minimizing the length of the longest common subsequence$$$^{\text{∗}}$$$ between two bracelets.

Formally, let $$$s$$$ and $$$t$$$ be two permutations of the original array $$$a$$$. We want to find $$$(s,t)$$$ that minimizes the length of the longest cyclic common subsequence, $$$f(s,t)$$$, defined by the following:

  • Consider all cyclic shifts of array $$$t$$$, denoted as $$$t_1,t_2,\dots,t_n$$$$$$^{\text{†}}$$$.
  • Let $$$\text{LCS}(s,t)$$$ be the length of the Longest Common Subsequence between $$$s$$$ and $$$t$$$. Then $$$$$$f(s,t) = \max_{1\le i \le n}\text{LCS}(s,t_i).$$$$$$

Unfortunately, Busy Beaver has too many seashells to find the most beautiful bracelet pairs by hand. Please help him!

$$$^{\text{∗}}$$$An array $$$s$$$ is a subsequence of an array $$$t$$$ if $$$s$$$ can be obtained from $$$t$$$ by deleting some (possibly none or all) elements from $$$t$$$, without reordering the remaining elements.

$$$^{\text{†}}$$$A cyclic shift $$$t_i$$$ of an array $$$t=[t^{(1)},t^{(2)},\dots,t^{(n)}]$$$ by $$$i$$$ places is given by $$$[t^{(1+i)},t^{(2+i)},\dots,t^{(n+i)}]$$$, where indices are taken modulo $$$n$$$.

Input

Each test contains multiple test cases. The first line of input contains a single integer $$$T$$$ $$$(1\le T\le 500)$$$, the number of test cases. The description of each test case follows.

The first line of each test case contains a single positive integer $$$N$$$ $$$(1\le N\le 500)$$$.

The second line of each test case contains $$$N$$$ integers $$$a_1,a_2,\dots, a_N$$$ $$$(1\le a_i\le 10^9)$$$ — the types of seashells Busy Beaver has collected.

It is guaranteed that the sum of $$$N$$$ across all test cases does not exceed $$$500$$$.

Output

For each test case, output two lines. The first line consists of $$$N$$$ integers $$$s_1,s_2,\dots,s_N$$$, and the second line consists of $$$N$$$ integers $$$t_1,t_2,\dots,t_N$$$, representing some $$$(s,t)$$$ that minimizes $$$f(s,t)$$$.

If there are multiple solutions, print any of them.

Example
Input
1
3
1 2 3
Output
1 2 3
1 3 2
Note

Note that $$$f([1,2,3],[1,3,2])$$$ is $$$2$$$ because $$$\text{LCS}([1,2,3],[1,3,2]) = 2$$$ ($$$[1,2]$$$ is a shared subsequence). This is the maximum $$$\text{LCS}$$$ over all cyclic shifts of $$$t$$$:

  • $$$\text{LCS}([1,2,3],[1,3,2]) = 2$$$ ($$$[1,2]$$$ is a shared subsequence).
  • $$$\text{LCS}([1,2,3],[3,2,1]) = 1$$$ ($$$[1]$$$ is a shared subsequence).
  • $$$\text{LCS}([1,2,3],[2,1,3]) = 2$$$ ($$$[2,3]$$$ is a shared subsequence).
It can be shown that there are no $$$s$$$ and $$$t$$$ that are permutations of $$$[1,2,3]$$$, such that $$$f(s,t) \le 1$$$.