409410: GYM103505 A Touch

A. Touchtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

ET Glob has an array of $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$. Unfortunately, he is unhappy with this array and, in his anger, wants to level it to the ground (i.e. make $$$a_1=a_2=\ldots = a_n=0$$$). While he could technically level the array instantly, ET Glob wants to make its death slow and painful. To achieve this, he wants to angrily touch the array. With one touch he can subtract $$$1$$$ from a particular element of the array and its neighbours. For example, if ET Glob angrily touches the third element of $$$a=\{5,6,7,8\}$$$, the array becomes $$$\{5,5,6,7\}$$$, whereas if he touches the first element, the array becomes $$$\{4,5,7,8\}$$$.

Please note that in the second example the last element remains unchanged, because it is not considered a neighbour of the first element.

You are given $$$t$$$ testcases. Each testcase contains an integer $$$n$$$ and an array $$$a$$$ of length $$$n$$$. For each testcase, ET Glob wants to know if he can flatten the array. If he can, print "YES", followed by $$$n$$$ integers, the $$$i$$$-th of which being the number of times ET Glob has to touch the $$$i$$$-th element of the array. Otherwise, simply print "NO".

Input

The first line of input contains one integer $$$t$$$ ($$$1 \le t \le 10^5$$$), the number of testcases. Each testcase consists of $$$2$$$ lines, the former containing one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$), and the latter containg $$$n$$$ integers, the elements of the array ($$$0 \le a_i \le 10^9$$$, for all $$$i \in [1,n]$$$).

It is guaranteed that the sum of all $$$n$$$ does not exceed $$$3 \cdot 10^5$$$ (i.e. $$$\sum n \le 3 \cdot 10^5$$$).Output

For each testcase, if ET Glob can flatten the array, print "YES", without the quotes, followed by the way the array can be flattened. Otherwise, print "NO", without the quotes.

Note: Capitalization doesn't matter, YeS, yEs and yes are all recognised as a positive answer. If there are multiple valid answers, you may print any.Scoring

• Subtask 1 (7 points): $$$1 \le n \le 3$$$;
• Subtask 1 (14 points): ET Glob doesn't need to touch the first element at all;
• Subtask 2 (33 points): $$$0 \le a_i \le 100$$$;
• Subtask 3 (46 points): No further constraints.

ExampleInput

6
8
5 6 8 7 9 8 9 6
2
5 6
1
7
7
3 6 4 5 6 7 5
3
8 8 0
9
5 9 6 8 8 10 7 5 4

Output

YES
0 5 1 2 4 3 1 5 
NO
YES
7 
YES
2 1 3 0 2 4 1 
YES
8 0 0 
NO