A Suitable Rearrangement#13121

A Suitable Rearrangement

2 seconds
256 megabytes

You are given an array of integers.

Determine whether its elements can be rearranged so that the resulting array satisfies

\sum_{j=1}^{i}b_j\le\max(b_1,b_2,\ldots,b_i)

for every 1\le i\le n. If possible, find any such rearrangement.

Input

The first line contains one integer (1\le t\le10^4) — the number of test cases.

The first line of each test case contains one integer (1\le n\le10^5) — the array length.

The second line contains integers a_1,a_2,\ldots,a_n (-10^9\le a_i\le10^9).

The sum of over all test cases does not exceed 10^5.

Output

For each test case, print NO if no suitable rearrangement exists.

Otherwise, print YES, followed on the next line by the elements of the resulting array. If there are several suitable rearrangements, print any of them.

You may print the letters in YES and NO in any case.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Note

In the first test case of the first example, the rearrangement [2,0,-1,-10,-7,8] has prefix sums 2,2,1,-9,-16,-8 and prefix maxima 2,2,2,2,2,8. All inequalities hold. In the second test case, no suitable rearrangement exists.

In the second example, an array with one element always satisfies the condition. An array of zeros also works. For , however, the sum of the entire array is , which exceeds its maximum .

Scoring

  1. Subtask ( points): t\le10, n\le10.

  2. Subtask ( points): n\le100.

  3. Subtask ( points): no additional constraints.