Description

Input

The first line of input data contains one number $t$ ($1 \leqslant t \leqslant 1000$) — the number of test cases.

In the first line of test case, one number is given $n$ ($1 \leqslant n \leqslant 100$) — the number of seconds during which Nikita's announcement hung on the main page.

The next line contains $n$ numbers $b_1, b_2, b_3, \ldots, b_n$ ($1 \leqslant |b_i| \leqslant n$) — mixed array $a$. It is guaranteed that there exists such a permutation of $b$ that it is a correct sequence of events described in the condition.

It is guaranteed that the sum of $n$ for all input test cases does not exceed $10^4$.

Output

For each test case, output two lines, each of which contains $n$ numbers.

In the first line, for each test case, output the maximum number of likes that Nikita could have at the announcement at the $i$th second.

In the second line, for each test case, output the minimum number of likes that Nikita could have at the announcement at the $i$th second.

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

1 2 1 
1 0 1 
1 0 
1 0 
1 2 3 4 3 2 
1 0 1 0 1 2 
1 2 3 4 3 
1 0 1 2 3 
1 2 3 4 5 4 3 
1 0 1 0 1 2 3

Note

In the first test case, the maximum values are reached with the following permutation: $1, 2, -2$. And the minimum values for such: $2, -2, 1$.

In the third test case, all maximal values are reached with the following permutation: $4, 2, 3, 1, -1, -2$. And the minimum values for the next permutation: $2, -2, 1, -1, 3, 4$.