ARRANGE - Arranging Amplifiers


Scientists at the TIFR, Mumbai, are doing some cutting edge research on the Propagation of Signals. A young researcher comes up with a method of progressively amplifying signals, as they progress along a path. The method involves the placing of Amplifiers at regular distances along the line. Each amplifier is loaded with a number a(i), which is called its amplification factor. The method of amplification is simple: an amplifier which recieves a signal of strength X, and has Y loaded in it, results in a signal of strength Y^X [ Y to the power X]. In course of his research, the young scientist tries to find out, that given a set of n amplifiers loaded with a(0), a(1), a(2), ...., a(n-1), which particular permutation of these amplifiers, when placed at successive nodes, with the initial node given a signal of strength 1, produces the strongest output signal.

this is better illustrated by the following example : 5 6 4
4^(5^(6^1)) is the strength of the strongest signal, which is generated by putting amplifier loaded with 6 in first place, 5 in second place and 4 in third place.

Given a list of integers specifying the set of amplifiers at hand, you must find out the order in which they must be placed, to get the highest signal strength. In case their exist multiple permutations with same output, you should print the one which has bigger amplifiers first.

Input

First line of input contains T, the number of test cases. For each test case first line contains a number ni, which is equal to the number of amplifiers available. Next line contains n integers, separated by spaces which denote the values with which the amplifiers are loaded.

Output

Output contains T lines, one for each test case. Each line contains ni integers, denoting the order in which the amplifiers should be kept such that the result is strongest.

Example

Input:
2
3
5 6 4
2
2 3

Output:
6 5 4
2 3

Constraints and Limits

T ≤ 20, Ni ≤ 10^5.
Each amplifier will be loaded with a positive integer p, 0 < p ≤ 10^9.
No two amplifier > 1 shall be loaded with the same integer.


hide comments
deepak_4: 2021-04-29 11:00:53

1 can be loaded many times , and rest all numbers can be loaded only once , please make the statement more clear

parthking: 2021-03-29 22:39:46

use double instead of int

legit_123: 2021-03-28 12:08:42

its giving tle on java

girsai: 2021-03-12 07:00:10

rather than reading question reading comments is better
here in comments we get better explanation

mayank_01: 2021-03-11 18:55:13

i dont understand this question bt got AC with the help of coments...

akshraj: 2021-02-26 19:23:39

for test case : 1 1 5 4 3 1 2 -> OUTPUT on Paper : 1 1 1 5 4 2 3
but in question accepted output is - 111 5 4 3 2
why ? Please check it whether I m correct or not

arafat_123: 2021-01-08 14:54:26

Super easy!!!! AC in one go.

ayush803: 2020-12-24 05:59:50

Take care of multiple 1

neerav1515: 2020-11-12 20:48:29

check for these test cases :
1 3 4 1 1 1 2 OUTPUT :- 1 1 1 1 4 3 2
1 3 2 1 1 1 1 OUTPUT :- 1 1 1 1 1 2 3

piperidine: 2020-11-09 19:48:24

took care of multiple ones and the case with 2 and 3 ...Still getting wrong answer :((


Added by:Ajay Somani
Date:2008-02-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:CodeCraft 08 Anshuman Singh