Тим Занятый Бобёр записался на курсы стрельбы из пистолета, чтобы выполнить требования по физкультуре, и хочет стать элитным стрелком. В тире MIT есть $N$ ($1 \le N \le 3 \cdot 10^5$) дорожек, пронумерованных от $1$ до $N$. На дорожке $i$ в данный момент в ряд выставлено $A_i$ ($0 \le A_i \le 5 \cdot 10^5$) мишеней. Гарантируется, что в тире есть хотя бы одна мишень.

У Тима бесконечный запас патронов, и ему нужно сбить все мишени. Перед каждым выстрелом Тим выбирает дорожку и делает $1$ выстрел по ней. Как только мишень поражена, она падает и больше не поднимается.

Однако Тим стреляет ужасно: каждый нечётный выстрел попадает в первую мишень на дорожке, а каждый чётный выстрел пролетает мимо первой мишени и попадает во вторую (если она существует). Первый выстрел считается выстрелом номер $1$.

Тиму запрещено делать выстрел, который не попадает ни в одну мишень, так как это повредит стену за мишенями. Помогите Тиму найти последовательность выстрелов, которая собьёт все мишени, или определите, что такой последовательности не существует.

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

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

Каждый из $t$ наборов состоит из $2$ строк. В первой строке содержится $N$, количество дорожек. Во второй строке содержатся $N$ целых чисел $A_1, A_2, \dots, A_n$, обозначающих количество мишеней на каждой дорожке.

Гарантируется, что сумма $A_i$ по всем наборам входных данных не превышает $5 \cdot 10^5$. Гарантируется, что сумма $N$ по всем наборам входных данных не превышает $3 \cdot 10^5$.

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

Для каждого набора данных выведите "YES", если существует последовательность выстрелов, сбивающая все мишени, или "NO", если такой последовательности не существует. Вы можете выводить ответ в любом регистре (верхнем или нижнем). Например, строки "yEs", "yes", "Yes" и "YES" будут распознаны как положительный ответ.

Пусть $A$ — сумма $A_i$ в наборе данных (заметьте, что $A$ может отличаться для разных наборов). Если такая последовательность существует, выведите на отдельной строке последовательность из $A$ целых чисел $l_1, l_2, \dots, l_A$, разделённых пробелами, где $l_i$ — номер дорожки, по которой нужно сделать $i$-й выстрел. Если решений несколько, выведите любое из них.

Подзадачи

Вы получите 50% баллов за каждую подзадачу, если ответы YES/NO верны, но предоставленные значения $l_i$ — нет. Для каждого набора данных вы должны вывести ровно $A$ значений $l_i$ для получения частичных баллов.

• (30 баллов): Сумма $N$ по всем наборам данных не превышает $2000$, и сумма $A_i$ по всем наборам данных не превышает $2000$.
• (70 баллов): Дополнительных ограничений нет.

Примеры

Пример 1

3
1
3
1
2
5
1 1 1 1 1

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

YES
1 1 1
NO
NO

Примечание

В первом наборе данных есть только $1$ дорожка с $3$ мишенями, и Wabbit может сбить все мишени, сделав $3$ выстрела по дорожке $1$. Если мишени — это $A, B$ и $C$ (от передней к задней), то первый выстрел собьёт $A$, второй выстрел пролетит мимо $B$ и собьёт $C$, а последний выстрел собьёт $B$.

Во втором наборе данных есть только $1$ дорожка с $2$ мишенями. Первый выстрел по дорожке $1$ попадёт в переднюю мишень, но второй выстрел не собьёт оставшуюся мишень, так как пролетит мимо. Таким образом, для этого набора данных последовательности выстрелов не существует.

В третьем наборе данных есть $5$ дорожек по $1$ мишени на каждой. Первый выстрел по любой дорожке собьёт мишень на этой дорожке, но второй выстрел не сможет попасть ни в какую другую мишень. Таким образом, для этого набора данных последовательности выстрелов не существует.