D. Шокирующая расстановка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a_1, a_2, \ldots, a_n$$$, состоящий из целых чисел, такой что $$$a_1 + a_2 + \ldots + a_n = 0$$$.

Переставьте элементы массива $$$a$$$ таким образом, чтобы выполнялось следующее условие:

$$$$$$\max\limits_{1 \le l \le r \le n} \lvert a_l + a_{l+1} + \ldots + a_r \rvert < \max(a_1, a_2, \ldots, a_n) - \min(a_1, a_2, \ldots, a_n),$$$$$$ где $$$|x|$$$ обозначает модуль числа $$$x$$$.

Более формально, вам нужно выяснить, существует ли такая перестановка $$$p_1, p_2, \ldots, p_n$$$, что для массива $$$a_{p_1}, a_{p_2}, \ldots, a_{p_n}$$$ выполняется условие выше, и найти полученный массив.

Напомним, что массив $$$p_1, p_2, \ldots, p_n$$$ называется перестановкой, если для каждого числа $$$x$$$ от $$$1$$$ до $$$n$$$ существует ровно одно $$$i$$$ от $$$1$$$ до $$$n$$$ такое, что $$$p_i = x$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 50\,000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 300\,000$$$) — длина массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — элементы массива $$$a$$$. Гарантируется, что сумма массива $$$a$$$ равняется нулю, иными словами: $$$a_1 + a_2 + \ldots + a_n = 0$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$300\,000$$$.

Выходные данные

Для каждого набора входных данных, если переставить элементы массива $$$a$$$ требуемым образом невозможно, в единственной строке выведите «No».

Если же это возможно, в первой строке выведите «Yes», а далее в отдельной строке $$$n$$$ чисел — элементы $$$a_1, a_2, \ldots, a_n$$$, переставленные в нужном порядке ($$$a_{p_1}, a_{p_2}, \ldots, a_{p_n}$$$).

Если возможных ответов несколько, вы можете вывести любой из них.

Пример
Входные данные
7
4
3 4 -2 -5
5
2 2 2 -3 -3
8
-3 -3 1 1 1 1 1 1
3
0 1 -1
7
-3 4 3 4 -4 -4 0
1
0
7
-18 13 -18 -17 12 15 13
Выходные данные
Yes
-5 -2 3 4
Yes
-3 2 -3 2 2
Yes
1 1 1 -3 1 1 1 -3
Yes
-1 0 1
Yes
4 -4 4 -4 0 3 -3
No
Yes
13 12 -18 15 -18 13 -17
Примечание

В первом наборе входных данных $$$\max(a_1, \ldots, a_n) - \min(a_1, \ldots, a_n) = 9$$$. Поэтому элементы можно переставить следующим образом: $$$[-5, -2, 3, 4]$$$. Несложно видеть, что для такой расстановки значение $$$\lvert a_l + \ldots + a_r \rvert$$$ всегда не больше $$$7$$$, а значит и меньше $$$9$$$.

Во втором наборе входных данных можно переставить элементы массива следующим образом: $$$[-3, 2, -3, 2, 2]$$$. Тогда максимальный модуль суммы будет достигаться на подмассиве $$$[-3, 2, -3]$$$, и будет равен $$$\lvert -3 + 2 + -3 \rvert = \lvert -4 \rvert = 4$$$, что меньше чем $$$5$$$.

В четвёртом тестовом примере любая перестановка массива $$$a$$$ подойдёт в качестве ответа, в том числе и $$$[-1, 0, 1]$$$.