VegiCat tiene una matriz de enteros $A = (a_{ij})$ de tamaño $n \times n$. Para cada $1 \le i, j \le n$:
- Si $i = j$, $i = 1$ o $j = 1$, entonces $a_{ij} = -1$.
- En caso contrario, $a_{ij}$ es un entero no negativo.
Ayuda a VegiCat a construir un grafo simple no dirigido $G$ con $n$ vértices, numerados de $1$ a $n$.
Para cada par de vértices distintos $i, j$ con $i > 1$ y $j > 1$, el grafo debe satisfacer la siguiente condición: después de eliminar los vértices $i$ y $j$, junto con todas las aristas que tengan un extremo en cualquiera de los dos vértices, deben quedar exactamente $a_{ij}$ aristas.
Cada par de vértices $i, j$ se considera por separado. Es decir, para cada par se comienza con $G$ antes de que se haya eliminado cualquier vértice o arista.
Se garantiza que existe al menos un grafo de este tipo. Si hay múltiples soluciones, imprime cualquiera de ellas.
Entrada
La primera línea contiene un entero $T$ ($1 \le T \le 6 \cdot 10^4$), el número de casos de prueba. A continuación sigue la descripción de los casos de prueba.
Para cada caso de prueba, la primera línea contiene un entero $n$ ($4 \le n \le 10^3$), que denota el número de vértices en el grafo.
Luego, cada una de las siguientes $n$ líneas contiene $n$ enteros separados por espacios $a_{ij}$ ($-1 \le a_{ij} \le \frac{(n-3)(n-2)}{2}$), que representan la matriz $A$ descrita en el enunciado.
Se garantiza que la suma total de $n^2$ en todos los casos de prueba no supera $1.2 \cdot 10^6$, y que existe al menos un grafo correspondiente a la matriz $A$.
Salida
Para cada caso de prueba, imprime la matriz de adyacencia del grafo que construyas. Imprime $n$ líneas, cada una con $n$ enteros separados por espacios. Cada entero debe ser $0$ o $1$. La entrada en la $i$-ésima fila y la $j$-ésima columna es $1$ si hay una arista entre los vértices $i$ y $j$, y $0$ en caso contrario. Si hay múltiples soluciones, imprime cualquiera de ellas.
Ejemplos
Entrada 1
2 5 -1 -1 -1 -1 -1 -1 -1 3 1 2 -1 3 -1 2 2 -1 1 2 -1 1 -1 2 2 1 -1 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 4 5 3 6 5 -1 4 -1 5 4 5 5 -1 5 5 -1 5 7 5 -1 3 4 5 -1 4 4 -1 6 5 7 4 -1 5 -1 5 5 5 4 5 -1
Salida 1
0 1 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 0 1 1 0 1 0 1 1 0 0 1 0 1 0 1 0 0 0 0 1 1 0 1 0 0
Nota
La matriz de entrada real solo tendrá un único espacio entre dos enteros. Los espacios adicionales en el ejemplo están diseñados para mejorar la legibilidad de la presentación.