Avoiding Zero Problem solution Codeforces Global Round 11

Avoiding Zero Problem solution Codeforces Global Round 11-

This Problem is taken from codeforces global round 11. This is a very simple problem and strongly recommended to try this problem yourself before jumping to a solution directly.

 Link of Problem-https://codeforces.com/contest/1427/problem/A

Problem statement-

 A. Avoiding Zero

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array of n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$.

You have to create an array of n$n$ integers b1,b2,…,bn$b_1,b_2,\dots ,b_n$ such that:

• The array b$b$ is a rearrangement of the array a$a$, that is, it contains the same values and each value appears the same number of times in the two arrays. In other words, the multisets {a1,a2,…,an}$\{a_1,a_2,\dots ,a_n\}$ and {b1,b2,…,bn}$\{b_1,b_2,\dots ,b_n\}$ are equal.

  For example, if a=[1,−1,0,1]$a=[1,-1,0,1]$, then b=[−1,1,1,0]$b=[-1,1,1,0]$ and b=[0,1,−1,1]$b=[0,1,-1,1]$ are rearrangements of a$a$, but b=[1,−1,−1,0]$b=[1,-1,-1,0]$ and b=[1,0,2,−3]$b=[1,0,2,-3]$ are not rearrangements of a$a$.

• For all k=1,2,…,n$k=1,2,\dots ,n$ the sum of the first k$k$ elements of b$b$ is nonzero. Formally, for all k=1,2,…,n$k=1,2,\dots ,n$, it must hold
  b1+b2+⋯+bk≠0.$$b_1+b_2+\cdots +b_k\ne 0.$$

If an array b1,b2,…,bn$b_1,b_2,\dots ,b_n$ with the required properties does not exist, you have to print NO.

Input

Each test contains multiple test cases. The first line contains an integer t$t$ (1≤t≤1000$1\le t\le 1000$) — the number of test cases. The description of the test cases follows.

The first line of each testcase contains one integer n$n$ (1≤n≤50$1\le n\le 50$)  — the length of the array a$a$.

The second line of each testcase contains n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (−50≤ai≤50$-50\le a_i\le 50$)  — the elements of a$a$.

Output

For each testcase, if there is not an array b1,b2,…,bn$b_1,b_2,\dots ,b_n$ with the required properties, print a single line with the word NO.

Otherwise print a line with the word YES, followed by a line with the n$n$ integers b1,b2,…,bn$b_1,b_2,\dots ,b_n$.

If there is more than one array b1,b2,…,bn$b_1,b_2,\dots ,b_n$ satisfying the required properties, you can print any of them.

Example

input

Copy

4
4
1 -2 3 -4
3
0 0 0
5
1 -1 1 -1 1
6
40 -31 -9 0 13 -40

output

Copy

YES
1 -2 3 -4
NO
YES
1 1 -1 1 -1
YES
-40 13 40 0 -9 -31

Note

Explanation of the first testcase: An array with the desired properties is b=[1,−2,3,−4]$b=[1,-2,3,-4]$. For this array, it holds:

• The first element of b$b$ is 1$1$.
• The sum of the first two elements of b$b$ is −1$-1$.
• The sum of the first three elements of b$b$ is 2$2$.
• The sum of the first four elements of b$b$ is −2$-2$.

Explanation of the second testcase: Since all values in a$a$ are 0$0$, any rearrangement b$b$ of a$a$ will have all elements equal to 0$0$ and therefore it clearly cannot satisfy the second property described in the statement (for example because b1=0$b_1=0$). Hence in this case the answer is NO.

Explanation of the third testcase: An array with the desired properties is b=[1,1,−1,1,−1]$b=[1,1,-1,1,-1]$. For this array, it holds:

• The first element of b$b$ is 1$1$.
• The sum of the first two elements of b$b$ is 2$2$.
• The sum of the first three elements of b$b$ is 1$1$.
• The sum of the first four elements of b$b$ is 2$2$.
• The sum of the first five elements of b$b$ is 1$1$.

Explanation of the fourth testcase: An array with the desired properties is b=[−40,13,40,0,−9,−31]$b=[-40,13,40,0,-9,-31]$. For this array, it holds:

• The first element of b$b$ is −40$-40$.
• The sum of the first two elements of b$b$ is −27$-27$.
• The sum of the first three elements of b$b$ is 13$13$.
• The sum of the first four elements of b$b$ is 13$13$.
• The sum of the first five elements of b$b$ is 4$4$.
• The sum of the first six elements of b$b$ is −27$-27$.

Solution-

According to the problem, it is not possible to make array B  if sum of all elements of array A is zero.

so if the sum of all elements of the array A is is zero we will simply print NO otherwise we will pint Yes.

Now our task is to print array B too. so we have two choices now either sum of all elements of array A is greater than 0 or less than 0. 

if sum >0 we will print array A in non-increasing order because in this case sum of element b at any point can not equal to 0. else we print array A in increasing order.

Code discussion It's a community where you people helps each other.

Join me on telegram-https://t.me/competitiveProgrammingDiscussion

Complete code of this Problem-