Tim le Busy Beaver s'est inscrit à un cours de tir au pistolet pour satisfaire ses exigences en éducation physique et souhaite devenir un tireur d'élite. Le stand de tir du MIT possède $N$ ($1 \le N \le 3 \cdot 10^5$) couloirs numérotés de 1 à $N$. Le couloir $i$ contient actuellement $A_i$ ($0 \le A_i \le 5 \cdot 10^5$) cibles alignées. Il est garanti qu'il y a au moins une cible dans tout le stand de tir.

L'arme d'entraînement de Tim dispose d'un nombre infini de balles, et il doit abattre toutes les cibles. Avant chaque tir, Tim choisit un couloir et tire 1 coup dans ce couloir. Une fois qu'une cible est touchée, elle est renversée et ne se relèvera jamais.

Cependant, la visée de Tim est terrible, donc chaque tir de numéro impair touchera la première cible du couloir, tandis que chaque tir de numéro pair manquera la première cible du couloir et touchera la deuxième (si elle existe). Le premier tir est le tir 1.

Tim n'est pas autorisé à effectuer un tir qui ne touche aucune cible, car cela endommagerait le mur derrière les cibles. Aidez Tim à trouver une séquence de tirs qui renversera toutes les cibles, ou indiquez qu'une telle séquence n'existe pas.

Entrée

Chaque test contient plusieurs cas de test. La première ligne contient un entier unique $t$ ($1 \le t \le 1000$) : le nombre de cas de test. La description des cas de test suit.

Chacun des $t$ cas de test consiste en 2 lignes. La première ligne contient $N$, le nombre de couloirs. La deuxième ligne contient $N$ entiers séparés par des espaces $A_1, A_2, \dots, A_n$, indiquant le nombre de cibles dans chaque couloir.

Il est garanti que la somme des $A_i$ sur tous les cas de test ne dépasse pas $5 \cdot 10^5$.

Il est garanti que la somme des $N$ sur tous les cas de test ne dépasse pas $3 \cdot 10^5$.

Sortie

Pour chaque cas de test, affichez "YES" s'il existe une séquence de tirs qui touche toutes les cibles, ou "NO" si aucune séquence de ce type n'existe. Vous pouvez afficher la réponse en majuscules ou en minuscules. Par exemple, les chaînes "yEs", "yes", "Yes" et "YES" seront reconnues comme des réponses positives.

Soit $A$ la somme des $A_i$ dans le cas de test (notez que $A$ peut être différent pour différents cas de test). Si une telle séquence existe, affichez sur une ligne séparée une séquence de $A$ entiers séparés par des espaces $l_1, l_2, \dots, l_A$, où $l_i$ est le couloir dans lequel Wabbit doit tirer le $i$-ème coup. S'il existe plusieurs solutions, affichez-en n'importe laquelle.

Sous-tâches

Vous recevrez 50 % des points pour chaque sous-tâche si les réponses YES/NO sont correctes, mais que les valeurs fournies de $l_i$ ne le sont pas. Pour chaque cas de test, vous devez afficher exactement $A$ valeurs de $l_i$ pour obtenir des points partiels.

• (30 points) : La somme des $N$ sur tous les cas de test ne dépasse pas 2000, et la somme des $A_i$ sur tous les cas de test ne dépasse pas 2000.
• (70 points) : Aucune contrainte supplémentaire.

Exemples

Entrée 1

3
1
3
1
2
5
1 1 1 1 1

Sortie 1

YES
1 1 1
NO
NO

Remarque

Dans le premier cas de test, il n'y a qu'un seul couloir avec 3 cibles, et Wabbit peut renverser toutes les cibles en tirant 3 coups dans le couloir 1. Si les cibles sont A, B et C de l'avant vers l'arrière, le premier tir renversera A, le deuxième tir manquera B et renversera C, et le dernier tir renversera B.

Dans le deuxième cas de test, il n'y a qu'un seul couloir avec 2 cibles. Le premier tir dans le couloir 1 touchera la cible avant, mais le deuxième tir ne renversera pas la cible restante car il manquera sa cible. Ainsi, aucune séquence de tirs n'existe pour ce cas de test.

Dans le troisième cas de test, il y a 5 couloirs avec 1 cible chacun. Le premier tir dans n'importe quel couloir touchera la cible de ce couloir, mais le deuxième tir ne pourra toucher aucune autre cible. Ainsi, aucune séquence de tirs n'existe pour ce cas de test.