310563: CF1852B. Imbalanced Arrays

B. Imbalanced Arraystime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Ntarsis has come up with an array $a$ of $n$ non-negative integers.

Call an array $b$ of $n$ integers imbalanced if it satisfies the following:

• $-n\le b_i\le n$, $b_i \ne 0$,
• there are no two indices $(i, j)$ ($1 \le i, j \le n$) such that $b_i + b_j = 0$,
• for each $1 \leq i \leq n$, there are exactly $a_i$ indices $j$ ($1 \le j \le n$) such that $b_i+b_j>0$, where $i$ and $j$ are not necessarily distinct.

Given the array $a$, Ntarsis wants you to construct some imbalanced array. Help him solve this task, or determine it is impossible.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.

The first line of each test case has a single integer $n$ ($1 \leq n \leq 10^5$).

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq n$).

It is guaranteed that the sum of $n$ across all test cases does not exceed $10^5$.

Output

For each test case, output "NO" if there exists no imbalanced array.

Otherwise, output "YES". Then, on the next line, output $n$ integers $b_1, b_2, \ldots, b_n$ where $b_i \neq 0$ for all $1 \leq i \leq n$ — an imbalanced array.

ExampleInput

5
1
1
4
1 4 3 4
3
0 1 0
4
4 3 2 1
3
1 3 1

Output

YES
1 
NO
YES
-3 1 -2 
YES
4 2 -1 -3 
YES
-1 3 -1

Note

For the first test case, $b = [1]$ is an imbalanced array. This is because for $i = 1$, there is exactly one $j$ ($j = 1$) where $b_1 + b_j > 0$.

For the second test case, it can be shown that there exists no imbalanced array.

For the third test case, $a = [0, 1, 0]$. The array $b = [-3, 1, -2]$ is an imbalanced array.

• For $i = 1$ and $i = 3$, there exists no index $j$ such that $b_i + b_j > 0$.
• For $i = 2$, there is only one index $j = 2$ such that $b_i + b_j > 0$ ($b_2 + b_2 = 1 + 1 = 2$).

Another possible output for the third test case could be $b = [-2, 1, -3]$.

题目大意：
Ntarsis有一个由n个非负整数组成的数组a。称一个由n个整数组成的数组b为不平衡的，如果它满足以下条件：
- -n≤bi≤n，bi≠0，
- 没有两个索引(i,j)（1≤i,j≤n）使得bi+bj=0，
- 对于每个1≤i≤n，恰好有ai个索引j（1≤j≤n）使得bi+bj>0，其中i和j不一定不同。
给定数组a，Ntarsis希望您构建一个不平衡的数组。帮助他完成这个任务，或者确定这是不可能的。

输入数据格式：
每个测试包含多个测试用例。第一行包含测试用例的数量t（1≤t≤10^5）。测试用例的描述如下。
每个测试用例的第一行有一个整数n（1≤n≤10^5）。
下一行包含n个整数a1,a2,…,an（0≤ai≤n）。
保证所有测试用例的n之和不超过10^5。

输出数据格式：
对于每个测试用例，如果不存在不平衡数组，则输出"NO"。
否则，输出"YES"。然后在下一行输出n个整数b1,b2,…,bn，其中对所有1≤i≤n，bi≠0——一个不平衡数组。

示例：
输入
```
5
1
1
4
1 4 3 4
3
0 1 0
4
4 3 2 1
3
1 3 1
```
输出
```
YES
1
NO
YES
-3 1 -2
YES
4 2 -1 -3
YES
-1 3 -1
```

注意：
对于第一个测试用例，b=[1]是一个不平衡数组。这是因为对于i=1，恰好有一个j（j=1）使得b1+bj>0。
对于第二个测试用例，可以证明不存在不平衡数组。
对于第三个测试用例，a=[0,1,0]。数组b=[-3,1,-2]是一个不平衡数组。
- 对于i=1和i=3，不存在索引j使得bi+bj>0。
- 对于i=2，只有一个索引j=2使得bi+bj>0（b2+b2=1+1=2）。
第三个测试用例的另一个可能的输出是b=[-2,1,-3]。题目大意： Ntarsis有一个由n个非负整数组成的数组a。称一个由n个整数组成的数组b为不平衡的，如果它满足以下条件： - -n≤bi≤n，bi≠0， - 没有两个索引(i,j)（1≤i,j≤n）使得bi+bj=0， - 对于每个1≤i≤n，恰好有ai个索引j（1≤j≤n）使得bi+bj>0，其中i和j不一定不同。 给定数组a，Ntarsis希望您构建一个不平衡的数组。帮助他完成这个任务，或者确定这是不可能的。 输入数据格式： 每个测试包含多个测试用例。第一行包含测试用例的数量t（1≤t≤10^5）。测试用例的描述如下。 每个测试用例的第一行有一个整数n（1≤n≤10^5）。 下一行包含n个整数a1,a2,…,an（0≤ai≤n）。 保证所有测试用例的n之和不超过10^5。 输出数据格式： 对于每个测试用例，如果不存在不平衡数组，则输出"NO"。 否则，输出"YES"。然后在下一行输出n个整数b1,b2,…,bn，其中对所有1≤i≤n，bi≠0——一个不平衡数组。 示例： 输入 ``` 5 1 1 4 1 4 3 4 3 0 1 0 4 4 3 2 1 3 1 3 1 ``` 输出 ``` YES 1 NO YES -3 1 -2 YES 4 2 -1 -3 YES -1 3 -1 ``` 注意： 对于第一个测试用例，b=[1]是一个不平衡数组。这是因为对于i=1，恰好有一个j（j=1）使得b1+bj>0。 对于第二个测试用例，可以证明不存在不平衡数组。 对于第三个测试用例，a=[0,1,0]。数组b=[-3,1,-2]是一个不平衡数组。 - 对于i=1和i=3，不存在索引j使得bi+bj>0。 - 对于i=2，只有一个索引j=2使得bi+bj>0（b2+b2=1+1=2）。 第三个测试用例的另一个可能的输出是b=[-2,1,-3]。