VegiCat possède une matrice d'entiers $A = (a_{ij})$ de taille $n \times n$. Pour tout $1 \le i, j \le n$ :
- Si $i = j$, $i = 1$ ou $j = 1$, alors $a_{ij} = -1$.
- Sinon, $a_{ij}$ est un entier positif ou nul.
Aidez VegiCat à construire un graphe simple non orienté $G$ comportant $n$ sommets, numérotés de $1$ à $n$.
Pour chaque paire de sommets distincts $i, j$ tels que $i > 1$ et $j > 1$, le graphe doit satisfaire la condition suivante : après avoir supprimé les sommets $i$ et $j$, ainsi que toutes les arêtes ayant une extrémité en l'un de ces deux sommets, il doit rester exactement $a_{ij}$ arêtes.
Chaque paire de sommets $i, j$ est considérée séparément. Autrement dit, pour chaque paire, on repart du graphe $G$ avant toute suppression de sommets ou d'arêtes.
Il est garanti qu'au moins un tel graphe existe. S'il existe plusieurs solutions, affichez n'importe laquelle d'entre elles.
Entrée
La première ligne contient un entier $T$ ($1 \le T \le 6 \cdot 10^4$), le nombre de cas de test. La description des cas de test suit.
Pour chaque cas de test, la première ligne contient un entier $n$ ($4 \le n \le 10^3$), désignant le nombre de sommets du graphe.
Ensuite, chacune des $n$ lignes suivantes contient $n$ entiers séparés par des espaces $a_{ij}$ ($-1 \le a_{ij} \le \frac{(n-3)(n-2)}{2}$), représentant la matrice $A$ décrite dans l'énoncé.
Il est garanti que la somme totale des $n^2$ sur l'ensemble des cas de test ne dépasse pas $1.2 \cdot 10^6$, et qu'il existe au moins un graphe correspondant à la matrice $A$.
Sortie
Pour chaque cas de test, affichez la matrice d'adjacence du graphe que vous construisez. Affichez $n$ lignes contenant chacune $n$ entiers séparés par des espaces. Chaque entier doit valoir $0$ ou $1$. L'élément situé à la $i$-ème ligne et à la $j$-ème colonne vaut $1$ s'il existe une arête entre les sommets $i$ et $j$, et $0$ sinon. S'il existe plusieurs solutions, affichez n'importe laquelle d'entre elles.
Exemples
Entrée 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
Sortie 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
Remarque
La matrice d'entrée réelle ne comportera qu'un seul espace entre deux entiers. Les espaces supplémentaires dans l'exemple sont uniquement destinés à améliorer la lisibilité de la mise en page.