Array Shuffling solution codeforces

Array Shuffling solution codeforces

 

oolimry has an array aa of length nn which he really likes. Today, you have changed his array to bb, a permutation of aa, to make him sad.

Because oolimry is only a duck, he can only perform the following operation to restore his array:

  • Choose two integers i,ji,j such that 1i,jn1≤i,j≤n.
  • Swap bibi and bjbj.

The sadness of the array bb is the minimum number of operations needed to transform bb into aa.

ALSO READ:-   Unequal Array solution codeforces

Given the array aa, find any array bb which is a permutation of aa that has the maximum sadness over all permutations of the array aa.

Input

Each test contains multiple test cases. The first line contains a single integer tt (1t1041≤t≤104)  — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer nn (1n21051≤n≤2⋅105)  — the length of the array.

ALSO READ:-   Pancake Deque solution codejam

The second line of each test case contains nn integers a1,a2,,ana1,a2,…,an (1ain1≤ai≤n)  — elements of the array aa.

It is guaranteed that the sum of nn over all test cases does not exceed 21052⋅105.

Output

For each test case, print nn integers b1,b2,,bnb1,b2,…,bn — describing the array bb. If there are multiple answers, you may print any.

Example
input

Copy
2
2
2 1
4
1 2 3 3
output

Copy
1 2
3 3 2 1

Leave a Comment