Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4102
Array in the Pocket

Time Limit: 2 Seconds      Memory Limit: 65536 KB

BaoBao has just found an array $A = \{a_1, a_2, \dots, a_n\}$ of $n$ integers in his left pocket. As BaoBao is bored, he decides to rearrange it into another array $B = \{b_1, b_2, \dots, b_n\}$ of $n$ integers such that $B$ is a permutation of $A$, and $a_i \ne b_i$ for all $1 \le i \le n$. Please help BaoBao finish the rearragement.

If multiple valid rearrangements exist, find the smallest one among them.

Consider two arrays $C = \{c_1, c_2, \dots, c_n\}$ and $D = \{d_1, d_2, \dots, d_n\}$, we say $C$ is smaller than $D$ if there exists an integer $k$ such that $1 \le k \le n$, $c_i = d_i$ for all $1 \le i < k$, and $c_k < d_k$.

Input

There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 10^5$), indicating the length of the array.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), indicating the given array.

Output

For each test case output one line containing $n$ integers $b_1, b_2, \dots, b_n$ separated by a space, indicating the answer. If there are multiple valid answers, output the smallest one. If no valid answer exists, print "Impossible" (without quotes) instead.

Please, DO NOT output extra spaces at the end of each line, or your answer may be considered incorrect!

Sample Input

3
4
4 1 3 2
4
1 1 2 3
3
1 1 1

Sample Output

1 2 4 3
2 3 1 1
Impossible

Author: WENG, Caizhi
Source: The 16th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple
Submit    Status