En la panadería real, el jefe de cocina decidió preparar la tortita más uniforme del mundo. Preparó una tortita con la forma de un polígono estrictamente convexo $A$, cuyos vértices $A_1,A_2,\ldots,A_n$ estaban enumerados en sentido antihorario.

Después, el ayudante del cocinero decidió «dejar la forma un poco más prolija»: marcó el punto medio de cada lado, conectó los puntos marcados en orden y cortó toda la masa que quedaba fuera del polígono resultante. El jefe de cocina ni siquiera tuvo tiempo de protestar antes de que el ayudante repitiera exactamente lo mismo una vez más.

Formalmente, primero se obtuvo el polígono $B$ a partir del polígono $A$:

$$B_i=\frac{A_i+A_{i+1}}{2},$$

y después se obtuvo el polígono $C$ a partir del polígono $B$ de la misma manera:

$$C_i=\frac{B_i+B_{i+1}}{2},$$

donde $A_{n+1}=A_1$ y $B_{n+1}=B_1$.

Ahora solo queda el polígono final $C$ sobre la mesa. El jefe de cocina está seguro de que el ayudante lo arruinó todo y exige que la tortita recupere la forma que tenía antes de los cortes. Mientras tanto, el ayudante lleva ya tres horas discutiendo sobre si acaso se podría haber preparado una tortita así.

Debes reconstruir cualquier polígono inicial $A$ adecuado, o indicar que no existe tal polígono.

Se garantiza que, si existe una respuesta, existe un polígono $A$ adecuado tal que ambas coordenadas de cada uno de sus vértices son enteras, divisibles por $4$ y no superan $10^9$ en valor absoluto.

Entrada

La primera línea contiene un único entero $t$ ($1\le t\le7500$): el número de casos de prueba. A continuación se describen los casos de prueba.

La primera línea de cada caso de prueba contiene un único entero $n$ ($3\le n\le1000$): el número de vértices del polígono.

Cada una de las siguientes $n$ líneas contiene dos enteros $x_i$ e $y_i$ ($|x_i|,|y_i|\le10^9$): las coordenadas del punto $C_i$.

Se garantiza que, en cada caso de prueba, los puntos $C_1,C_2,\ldots,C_n$ forman un polígono estrictamente convexo y están enumerados en sentido antihorario.

Se garantiza que la suma de $n$ sobre todos los casos de prueba no supera $10^5$.

Salida

Para cada caso de prueba, imprime la respuesta.

Si no existe un polígono inicial adecuado, imprime NO.

En caso contrario, imprime YES. Después imprime $n$ líneas; la $i$-ésima debe contener dos coordenadas del punto $A_i$ separadas por un espacio. Las coordenadas de los puntos pueden ser números reales cuyo valor absoluto no supere $4\cdot10^9$. Los puntos impresos deben formar un polígono estrictamente convexo en sentido antihorario. Además, para todo $i$ debe cumplirse la siguiente desigualdad:

$$[(A_{i+1}-A_i),(A_{i+2}-A_{i+1})]>10^{-7},$$

donde los índices se toman módulo $n$, y

$$[V,U]=V_xU_y-V_yU_x.$$

Tu respuesta se considera correcta si, después de aplicar dos veces la operación descrita al polígono que imprimiste, ambas coordenadas del $i$-ésimo punto resultante coinciden con las coordenadas del punto $C_i$ con un error absoluto o relativo de como máximo $10^{-6}$.

Puedes imprimir YES y NO con cualquier combinación de mayúsculas y minúsculas. Por ejemplo, las cadenas yEs, yes, Yes y YES se reconocerán como respuestas afirmativas.

Ejemplos

Entrada 1

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

Salida 1

YES
0 0
8 4
4 8
YES
0 0.5
4 -0.5
4 4.5
0 3.5
NO

Nota

Ilustración del segundo caso de prueba: uno de los posibles polígonos $A$ que genera el polígono $C$ requerido: