A. Absolute Winnema
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This problem has nothing to do with problem F

Danna has N friends, numbered from $$$1$$$ to $$$N$$$ in a fixed line order. She wants to give $$$X_i$$$ candies to the $$$i$$$-th friend ($$$1 \le i \le N$$$).

A friend $$$i$$$ is defined as an "Absolute Winner" if the number of candies they receive $$$X_i$$$ is strictly greater than the sum of all candies given to every friend standing before them in line (i.e., $$$X_i \gt \sum_{k=1}^{i-1} X_k$$$). Note that by definition, the 1st friend ($$$i = 1$$$) is always an Absolute Winner since the sum of candies before them is 0, so $$$X_1 \gt 0$$$.

However, some friends are very picky. For each friend $$$i$$$, you are given a requirement $$$A_i$$$:

1. If $$$A_i = -1$$$, friend $$$i$$$ is open to receiving any positive integer number of candies.

2. If $$$A_i \gt 0$$$, friend $$$i$$$ demands to receive exactly $$$A_i$$$ candies (i.e., $$$X_i = A_i$$$).

Your task is to determine whether Danna can distribute positive integer amounts of candies $$$(X_1, X_2, \dots, X_N)$$$ such that:

1. Every friend $$$i$$$ is an Absolute Winner ($$$X_i \gt \sum_{k=1}^{i-1} X_k$$$).

2. Every picky friend's requirement is satisfied ($$$X_i = A_i$$$ whenever $$$A_i \neq -1$$$).

3. $$$X_i$$$ is a positive integer ($$$1 \le X_i \le 10^9$$$) for all $$$1 \le i \le N$$$.

If it is possible to satisfy all conditions, print "Yes" followed by any valid assignment of candies $$$X_1, X_2, \dots, X_N$$$. Otherwise, print "No".

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of friends.

The second line of each test case contains $$$n$$$ space-separated integers $$$A_1, A_2, \dots, A_n$$$ ($$$A_i = -1$$$ or $$$1 \le A_i \le 10^9$$$) — representing the requirement for the $$$i$$$-th friend.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case:

  • Print "No" on a single line if it is impossible to satisfy all conditions.
  • Otherwise, print "Yes" on the first line, and on the second line print $$$n$$$ space-separated integers $$$X_1, X_2, \dots, X_n$$$ ($$$1 \le X_i \le 10^9$$$) representing a valid distribution of candies.
Example
Input
5
1
1989
4
-1 -1 -1 -1
10
-1 -1 -1 -1 -1 -1 -1 -1 -1 1
2
1 1
2
999999999 -1
Output
YES
1989 
YES
10 12 25 1000 
NO
NO
YES
999999999 1000000000