D. Shocking Arrangementtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given an array a_1, a_2, \ldots, a_n consisting of integers such that a_1 + a_2 + \ldots + a_n = 0.You have to rearrange the elements of the array a so that the following condition is satisfied:\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), where |x| denotes the absolute value of x.More formally, determine if there exists a permutation p_1, p_2, \ldots, p_n that for the array a_{p_1}, a_{p_2}, \ldots, a_{p_n}, the condition above is satisfied, and find the corresponding array.Recall that the array p_1, p_2, \ldots, p_n is called a permutation if for each integer x from 1 to n there is exactly one i from 1 to n such that p_i = x.InputEach test contains multiple test cases. The first line contains the number of test cases t (1 \le t \le 50\,000). The description of the test cases follows.The first line of each test case contains a single integer n (1 \le n \le 300\,000) — the length of the array a.The second line of each test case contains n integers a_1, a_2, \ldots, a_n (-10^9 \le a_i \le 10^9) — elements of the array a. It is guaranteed that the sum of the array a is zero, in other words: a_1 + a_2 + \ldots + a_n = 0.It is guaranteed that the sum of n over all test cases does not exceed 300\,000.OutputFor each test case, if it is impossible to rearrange the elements of the array a in the required way, print "No" in a single line.If possible, print "Yes" in the first line, and then in a separate line n numbers — elements a_1, a_2, \ldots, a_n rearranged in a valid order (a_{p_1}, a_{p_2}, \ldots, a_{p_n}).If there are several possible answers, you can output any of them.ExampleInput
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
Output
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
NoteIn the first test case \max(a_1, \ldots, a_n) - \min(a_1, \ldots, a_n) = 9. Therefore, the elements can be rearranged as [-5, -2, 3, 4]. It is easy to see that for such an arrangement \lvert a_l + \ldots + a_r \rvert is always not greater than 7, and therefore less than 9.In the second test case you can rearrange the elements of the array as [-3, 2, -3, 2, 2]. Then the maximum modulus of the sum will be reached on the subarray [-3, 2, -3], and will be equal to \lvert -3 + 2 + -3 \rvert = \lvert -4 \rvert = 4, which is less than 5.In the fourth test example, any rearrangement of the array a will be suitable as an answer, including [-1, 0, 1].
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 
['constructive algorithms', 'greedy', 'math', '*1600']