CF1798D.Shocking Arrangement

You 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$.

Each 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$ .

For 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.

In 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]$ .