У VegiCat есть целочисленная матрица $A = (a_{ij})$ размера $n \times n$. Для всех $1 \le i, j \le n$:
- Если $i = j$, $i = 1$ или $j = 1$, то $a_{ij} = -1$.
- В противном случае $a_{ij}$ — неотрицательное целое число.
Помогите VegiCat построить неориентированный простой граф $G$ с $n$ вершинами, пронумерованными от $1$ до $n$.
Для каждой пары различных вершин $i, j$ с $i > 1$ и $j > 1$ граф должен удовлетворять следующему условию: после удаления вершин $i$ и $j$ вместе со всеми рёбрами, имеющими конец хотя бы в одной из этих вершин, должно остаться ровно $a_{ij}$ рёбер.
Каждая пара вершин $i, j$ рассматривается отдельно. То есть для каждой пары мы начинаем с исходного графа $G$ до удаления каких-либо вершин или рёбер.
Гарантируется, что хотя бы один такой граф существует. Если решений несколько, выведите любое из них.
Входные данные
Первая строка содержит целое число $T$ ($1 \le T \le 6 \cdot 10^4$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Для каждого набора входных данных первая строка содержит целое число $n$ ($4 \le n \le 10^3$), обозначающее количество вершин в графе.
Затем каждая из следующих $n$ строк содержит $n$ разделённых пробелами целых чисел $a_{ij}$ ($-1 \le a_{ij} \le \frac{(n-3)(n-2)}{2}$), задающих матрицу $A$, описанную в условии.
Гарантируется, что общая сумма $n^2$ по всем наборам входных данных не превосходит $1.2 \cdot 10^6$, а также что существует хотя бы один граф, соответствующий матрице $A$.
Выходные данные
Для каждого набора входных данных выведите матрицу смежности построенного вами графа. Выведите $n$ строк, каждая из которых содержит $n$ целых чисел, разделённых пробелами. Каждое число должно быть равно $0$ или $1$. Элемент в $i$-й строке и $j$-м столбце равен $1$, если между вершинами $i$ и $j$ есть ребро, и $0$ в противном случае. Если решений несколько, выведите любое из них.
Примеры
Входные данные 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
Выходные данные 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
Примечание
В реальных входных данных между двумя соседними числами матрицы будет ровно один пробел. Дополнительные пробелы в примере добавлены для наглядности форматирования.