Tim, el castor ocupado, se ha inscrito en una clase de pistola para cumplir con su requisito de educación física y quiere ser un tirador de élite. El campo de tiro del MIT tiene $N$ ($1 \le N \le 3 \cdot 10^5$) carriles numerados del 1 al $N$. El carril $i$ tiene actualmente $A_i$ ($0 \le A_i \le 5 \cdot 10^5$) blancos alineados en una fila. Se garantiza que hay al menos un blanco en todo el campo de tiro.
El arma de práctica de Tim tiene un número infinito de balas y necesita derribar todos los blancos. Antes de cada disparo, Tim elegirá un carril y disparará 1 tiro por ese carril. Una vez que un blanco es alcanzado, será derribado y nunca volverá a levantarse.
Sin embargo, la puntería de Tim es terrible, por lo que cada disparo de número impar alcanzará al primer blanco en el carril, mientras que cada disparo de número par fallará al primer blanco en el carril y alcanzará al segundo (si existe). El primer disparo es el disparo 1.
A Tim no se le permite realizar un disparo que no alcance ningún blanco, ya que dañaría la pared detrás de los blancos. Ayuda a Tim a encontrar una secuencia de disparos que derribe todos los blancos, o indica que no existe tal secuencia.
Entrada
Cada prueba contiene múltiples casos de prueba. La primera línea contiene un único entero $t$ ($1 \le t \le 1000$): el número de casos de prueba. A continuación se describe cada caso de prueba.
Cada uno de los $t$ casos de prueba consta de 2 líneas. La primera línea contiene $N$, el número de carriles. La segunda línea contiene $N$ enteros separados por espacios $A_1, A_2, \dots, A_n$, que indican el número de blancos en cada carril.
Se garantiza que la suma de $A_i$ en todos los casos de prueba no supera $5 \cdot 10^5$. Se garantiza que la suma de $N$ en todos los casos de prueba no supera $3 \cdot 10^5$.
Salida
Para cada caso de prueba, imprime "YES" si existe una secuencia de disparos que alcance todos los blancos, o "NO" si no existe tal secuencia. Puedes imprimir la respuesta en cualquier formato (mayúsculas o minúsculas). Por ejemplo, las cadenas "yEs", "yes", "Yes" y "YES" serán reconocidas como respuestas positivas.
Sea $A$ la suma de $A_i$ en el caso de prueba (ten en cuenta que $A$ puede ser diferente para distintos casos de prueba). Si existe tal secuencia, imprime en una línea separada una secuencia de $A$ enteros separados por espacios $l_1, l_2, \dots, l_A$, donde $l_i$ es el carril al que Wabbit debe disparar el $i$-ésimo tiro. Si hay múltiples soluciones, imprime cualquiera de ellas.
Subtareas
Recibirás el 50% de los puntos de cada subtarea si las respuestas YES/NO son correctas, pero los valores proporcionados de $l_i$ no lo son. Para cada caso de prueba, debes imprimir exactamente $A$ valores de $l_i$ para obtener crédito parcial.
- (30 puntos): La suma de $N$ en todos los casos de prueba no supera 2000, y la suma de $A_i$ en todos los casos de prueba no supera 2000.
- (70 puntos): Sin restricciones adicionales.
Ejemplos
Entrada 1
3 1 3 1 2 5 1 1 1 1 1
Salida 1
YES 1 1 1 NO NO
Nota
En el primer caso de prueba, solo hay 1 carril con 3 blancos, y Wabbit puede derribar todos los blancos disparando 3 tiros al carril 1. Si los blancos son $A, B$ y $C$ de adelante hacia atrás, el primer disparo derribará a $A$, el segundo disparo fallará a $B$ y derribará a $C$, y el último disparo derribará a $B$.
En el segundo caso de prueba, solo hay 1 carril con 2 blancos. El primer disparo al carril 1 alcanzará al blanco frontal, pero el segundo disparo no derribará el blanco restante ya que fallará. Por lo tanto, no existe una secuencia de disparos para este caso de prueba.
En el tercer caso de prueba, hay 5 carriles con 1 blanco cada uno. El primer disparo a cualquier carril alcanzará el blanco en ese carril, pero el segundo disparo no podrá alcanzar ningún otro blanco. Por lo tanto, no existe una secuencia de disparos para este caso de prueba.