Складна гра#12292

Складна гра

1 секунда

256 мегабайтів

Середня

Фатех — дуже сердитий хлопець.

Фатех грав у гру влітку. Це була FPS гра CubeWarfare. Вона має $n$ раундів, і він може отримати бали в кожному раунді. Але оскільки він був дуже сердитий, коли він отримує негативні бали, він ламає ноутбук і не може грати наступні $2$ раунди. Його друг Осман не хоче, щоб він програвав, тому вирішив перерозподілити раунди. Оскільки він зайнятий, він попросив вас допомогти в цьому.

Вхідні дані

Перший рядок містить ціле число $t$ $(1 \leq t \leq 1 0^{4})$ (1 \le t \le 10^4) — кількість тестових випадків.

Кожен тестовий випадок складається з двох рядків:

Перший рядок містить одне ціле число $n (1 \leq n \leq 2 \cdot 1 0^{5})$ n(1 \le n \le 2 \cdot 10^5) — довжина масиву.

Другий рядок містить $n$ цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ a_{1},a_{2},…,a_{n} $(- 1 0^{9} \leq a_{i} \leq 1 0^{9})$ (-10^9 \le a_{i} \le 10^9) — бали, які він отримає після кожного раунду.

Гарантується, що сума $n$ по всіх тестових випадках не перевищує $2 \cdot 1 0^{5}$ 2 \cdot 10^5.

Вихідні дані

Для кожного тестового випадку виведіть будь-яку перестановку масиву $a$ — $b_{1}, b_{2}, b_{3}, ..., b_{n}$ b_1,b_2,b_3,...,b_n, яка досягає максимальної кількості балів, які отримує Фатех.

Якщо така перестановка не існує, виведіть $- 1$ .

Приклади

Приклад 1

Примітка

Результат першого тестового випадку виглядає наступним чином:

Фатех отримує $5$ балів, всього $5$ балів.
Фатех отримує $3$ бали, всього $8$ балів.
Фатех отримує $2$ бали, всього $10$ балів.
Фатех отримує $- 1$ бал, він розлютився і отримав $9$ балів, тепер він пропустить наступні два раунди, і оскільки більше ігор не залишилося, він не може грати далі.

Максимальний рахунок, який він отримує, становить $9$ .

Оцінювання

Підзадача $1$ ( $20$ балів) : $(1 \leq n \leq 8)$ (1 \le n \le 8) і $(1 \leq t \leq 100)$ (1 \le t \le 100)
Підзадача $2$ ( $30$ балів) : $(0 \leq a_{i} \leq 1 0^{9})$ (0 \le a_i \le 10^9)
Підзадача $3$ ( $150$ балів) : Без додаткових обмежень