Want to solve the contest problems after the official contest ends? Just register for practice and you will be able to submit solutions.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Challenging Cliffs

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are a game designer and want to make an obstacle course. The player will walk from left to right. You have $$$n$$$ heights of mountains already selected and want to arrange them so that the absolute difference of the heights of the first and last mountains is as small as possible.

In addition, you want to make the game difficult, and since walking uphill or flat is harder than walking downhill, the difficulty of the level will be the number of mountains $$$i$$$ ($$$1 \leq i < n$$$) such that $$$h_i \leq h_{i+1}$$$ where $$$h_i$$$ is the height of the $$$i$$$-th mountain. You don't want to waste any of the mountains you modelled, so you have to use all of them.

From all the arrangements that minimize $$$|h_1-h_n|$$$, find one that is the most difficult. If there are multiple orders that satisfy these requirements, you may find any.

Input

The first line will contain a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the number of mountains.

The second line of each test case contains $$$n$$$ integers $$$h_1,\ldots,h_n$$$ ($$$1 \leq h_i \leq 10^9$$$), where $$$h_i$$$ is the height of the $$$i$$$-th mountain.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output $$$n$$$ integers — the given heights in an order that maximizes the difficulty score among all orders that minimize $$$|h_1-h_n|$$$.

If there are multiple orders that satisfy these requirements, you may output any.

Example

Input

2 4 4 2 1 2 2 3 1

Output

2 4 1 2 1 3

Note

In the first test case:

The player begins at height $$$2$$$, next going up to height $$$4$$$ increasing the difficulty by $$$1$$$. After that he will go down to height $$$1$$$ and the difficulty doesn't change because he is going downhill. Finally the player will go up to height $$$2$$$ and the difficulty will increase by $$$1$$$. The absolute difference between the starting height and the end height is equal to $$$0$$$ and it's minimal. The difficulty is maximal.

In the second test case:

The player begins at height $$$1$$$, next going up to height $$$3$$$ increasing the difficulty by $$$1$$$. The absolute difference between the starting height and the end height is equal to $$$2$$$ and it's minimal as they are the only heights. The difficulty is maximal.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/19/2021 02:21:13 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|