VegiCat có một ma trận nguyên $A = (a_{ij})$ kích thước $n \times n$. Với mỗi $1 \le i, j \le n$:
- Nếu $i = j$, $i = 1$, hoặc $j = 1$, thì $a_{ij} = -1$.
- Ngược lại, $a_{ij}$ là một số nguyên không âm.
Hãy giúp VegiCat dựng một đồ thị đơn vô hướng $G$ gồm $n$ đỉnh, được đánh số từ $1$ đến $n$.
Với mọi cặp đỉnh phân biệt $i, j$ thỏa mãn $i > 1$ và $j > 1$, đồ thị phải thỏa mãn điều kiện sau: sau khi xóa hai đỉnh $i$ và $j$, cùng với tất cả các cạnh có một đầu mút tại một trong hai đỉnh này, phải còn lại đúng $a_{ij}$ cạnh.
Mỗi cặp đỉnh $i, j$ được xét riêng biệt. Nghĩa là, với mỗi cặp, ta bắt đầu từ đồ thị $G$ trước khi bất kỳ đỉnh hay cạnh nào bị xóa.
Dữ liệu đảm bảo luôn tồn tại ít nhất một đồ thị như vậy. Nếu có nhiều lời giải, hãy in ra một lời giải bất kỳ.
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 6 \cdot 10^4$), là số lượng bộ dữ liệu. Mô tả của các bộ dữ liệu theo sau.
Với mỗi bộ dữ liệu, dòng đầu tiên chứa một số nguyên $n$ ($4 \le n \le 10^3$), biểu thị số đỉnh của đồ thị.
Mỗi dòng trong $n$ dòng tiếp theo chứa $n$ số nguyên cách nhau bởi dấu cách $a_{ij}$ ($-1 \le a_{ij} \le \frac{(n-3)(n-2)}{2}$), biểu diễn ma trận $A$ được mô tả trong đề bài.
Dữ liệu đảm bảo tổng của $n^2$ trên tất cả các bộ dữ liệu không vượt quá $1.2 \cdot 10^6$, và tồn tại ít nhất một đồ thị tương ứng với ma trận $A$.
Dữ liệu ra
Với mỗi bộ dữ liệu, hãy in ra ma trận kề của đồ thị mà bạn dựng được. In ra $n$ dòng, mỗi dòng chứa $n$ số nguyên cách nhau bởi dấu cách. Mỗi số nguyên phải là $0$ hoặc $1$. Phần tử ở hàng thứ $i$ và cột thứ $j$ bằng $1$ nếu có cạnh nối giữa đỉnh $i$ và đỉnh $j$, và bằng $0$ trong trường hợp ngược lại. Nếu có nhiều lời giải, hãy in ra một lời giải bất kỳ.
Ví dụ
Dữ liệu vào 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
Dữ liệu ra 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
Ghi chú
Ma trận đầu vào thực tế sẽ chỉ có một dấu cách duy nhất giữa hai số nguyên. Các dấu cách thêm trong ví dụ được thiết kế để tăng tính dễ đọc của bố cục.