B. Несбалансированные массивы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ntarsis придумал массив $$$a$$$ из $$$n$$$ неотрицательных целых чисел.

Массив $$$b$$$ из $$$n$$$ целых чисел называется несбалансированным, если он удовлетворяет следующим условиям:

  • $$$-n\le b_i\le n$$$, $$$b_i \ne 0$$$,
  • не существует двух индексов $$$(i, j)$$$ ($$$1 \le i, j \le n$$$), таких что $$$b_i + b_j = 0$$$,
  • для каждого $$$1 \leq i \leq n$$$, существует ровно $$$a_i$$$ индексов $$$j$$$ ($$$1 \le j \le n$$$) таких, что $$$b_i+b_j>0$$$, где $$$i$$$ и $$$j$$$ не обязательно различны.

Дан массив $$$a$$$. Ntarsis хочет, чтобы вы построили любой несбалансированный массив. Помогите ему решить эту задачу или определите, что это невозможно.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

Следующая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq n$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам не превышает $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите «NO», если не существует несбалансированного массива.

В противном случае выведите «YES». Затем, на следующей строке, выведите $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$, где $$$b_i \neq 0$$$ для всех $$$1 \leq i \leq n$$$ — допустимый несбалансированный массив.

Пример
Входные данные
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$$$), где $$$b_1 + b_j > 0$$$.

Для второго набора можно показать, что не существует допустимого несбалансированного массива.

Для третьего набора, $$$a = [0, 1, 0]$$$. Массив $$$b = [-3, 1, -2]$$$ является допустимым несбалансированным массивом.

  • Для $$$i = 1$$$ и $$$i = 3$$$ не существует индекса $$$j$$$ такого, что $$$b_i + b_j > 0$$$.
  • Для $$$i = 2$$$ существует только один индекс $$$j = 2$$$, такой что $$$b_i + b_j > 0$$$ ($$$b_2 + b_2 = 1 + 1 = 2$$$).
Другой возможный ответ на третий пример — $$$b = [-2, 1, -3]$$$.