
ZOJ Problem Set  4102
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$. InputThere 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. OutputFor 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 Input3 4 4 1 3 2 4 1 1 2 3 3 1 1 1 Sample Output1 2 4 3 2 3 1 1 Impossible Author: WENG, Caizhi Source: The 16th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple 