VegiCat hat eine ganzzahlige $n \times n$-Matrix $A = (a_{ij})$. Für alle $1 \le i, j \le n$ gilt:
- Falls $i = j$, $i = 1$ oder $j = 1$ ist, gilt $a_{ij} = -1$.
- Andernfalls ist $a_{ij}$ eine nichtnegative ganze Zahl.
Hilf VegiCat dabei, einen ungerichteten einfachen Graphen $G$ mit $n$ Knoten zu konstruieren, die von $1$ bis $n$ nummeriert sind.
Für jedes Paar verschiedener Knoten $i, j$ mit $i > 1$ und $j > 1$ muss der Graph die folgende Bedingung erfüllen: Nach dem Löschen der Knoten $i$ und $j$ sowie aller Kanten, die einen Endpunkt in einem dieser beiden Knoten haben, müssen genau $a_{ij}$ Kanten übrig bleiben.
Jedes Knotenpaar $i, j$ wird separat betrachtet. Das heißt, für jedes Paar beginnt man mit dem ursprünglichen Graphen $G$, bevor irgendwelche Knoten oder Kanten gelöscht wurden.
Es wird garantiert, dass mindestens ein solcher Graph existiert. Falls es mehrere Lösungen gibt, gib eine beliebige davon aus.
Eingabe
Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 6 \cdot 10^4$), die Anzahl der Testfälle. Es folgt die Beschreibung der Testfälle.
Für jeden Testfall enthält die erste Zeile eine ganze Zahl $n$ ($4 \le n \le 10^3$), welche die Anzahl der Knoten im Graphen bezeichnet.
Jede der nächsten $n$ Zeilen enthält $n$ durch Leerzeichen getrennte ganze Zahlen $a_{ij}$ ($-1 \le a_{ij} \le \frac{(n-3)(n-2)}{2}$), welche die in der Aufgabenstellung beschriebene Matrix $A$ darstellen.
Es wird garantiert, dass die Gesamtsumme von $n^2$ über alle Testfälle $1.2 \cdot 10^6$ nicht überschreitet und dass mindestens ein zur Matrix $A$ passender Graph existiert.
Ausgabe
Gib für jeden Testfall die Adjazenzmatrix des von dir konstruierten Graphen aus. Gib $n$ Zeilen aus, die jeweils $n$ durch Leerzeichen getrennte ganze Zahlen enthalten. Jede ganze Zahl muss entweder $0$ oder $1$ sein. Der Eintrag in der $i$-ten Zeile und $j$-ten Spalte ist $1$, falls eine Kante zwischen den Knoten $i$ und $j$ existiert, und andernfalls $0$. Falls es mehrere Lösungen gibt, gib eine beliebige davon aus.
Beispiele
Eingabe 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
Ausgabe 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
Hinweis
In der tatsächlichen Eingabematrix befindet sich zwischen zwei ganzen Zahlen jeweils nur ein einziges Leerzeichen. Die zusätzlichen Leerzeichen im Beispiel dienen lediglich der besseren Lesbarkeit des Layouts.