The koalas enjoy playing all kinds of games with each other. One such game is played in the shifty koala underground, where fortunes can be lost or won in a single moment.
The game begins with a list of numbers , arranged into a row. Two players take turns picking either the number at the beginning or end of the row. In this variation of the game, each koala tries to maximize the sum of all the values that they pick. As the koalas have been playing this game since the beginning of time, they are masters and will always play optimally. Keen Ken Googler the Keen koala is keen to kollect as much kash as possible. Given his friendliness with the card dealer, he can arrange the numbers in any way that he wants before playing against his unfortunate victim. As a holder of the premium gamer club member card, he also always goes first.
However, Keen Ken is not very good at games, so he asks you to help him rearrange the numbers in into an arrangement such that he will always win if he plays optimally. Since Keen Ken has a lot of players to scam, help him do this times!
Keen Ken wins the game if the sum of all his chosen numbers is strictly greater than the sum of his opponent's numbers.
For this problem, Python users are recommended to use PyPy over CPython.
The first line contains the integer , the number of cases you are to solve.
Each test case consists of two lines. The first contains for that specific test case, followed by space-separated integers on the next line.
Output lines, each containing space-separated integers . Note that any arrangement suffices as long as Ken wins if he plays optimally. If Keen Ken cannot win, output .
Note: There should be no trailing whitespaces after each line and the output should end with a newline.
Sample Input 1
1 5 8 6 2 8 1
Sample Output 1
8 2 6 8 1
Explanation for Sample 1
At the end of the game, Ken receives a score of from the numbers , , and . The other player ends with a score of , using and . We see that is greater than so Ken wins.
Sample Input 2
1 6 4 7 4 6 8 3
Sample Output 2
6 7 4 4 8 3