Busy Beaver đang chơi với một đồ thị vô hướng, liên thông, không trọng số với $N$ ($2 \le N \le 500$) đỉnh được đánh số từ 1 đến $N$. Với mỗi cặp đỉnh $1 \le i < j \le N$, cậu ấy ghi lại độ dài đường đi ngắn nhất $A_{i,j}$ từ đỉnh $i$ đến đỉnh $j$ vào một tờ giấy ăn. Nhận thấy tất cả các con số này chiếm quá nhiều diện tích trên giấy, Busy Beaver quyết định chỉ ghi lại $B_{i,j}$, giá trị của $A_{i,j} \pmod 5$ lên giấy.

Hiện tại, Busy Beaver đã làm mất đồ thị của mình và chỉ còn lại tờ giấy ăn với các giá trị $B_{i,j}$ đã ghi. Hãy giúp Busy Beaver khôi phục một đồ thị khả thi, hoặc xác định rằng không tồn tại đồ thị như vậy và cậu ấy đã nhầm lẫn.

Một cách hình thức, cho trước $N$ và $B_{i,j}$ với $0 \le B_{i,j} < 5$, hãy quyết định xem có tồn tại một đồ thị vô hướng, liên thông, không trọng số với $N$ đỉnh sao cho độ dài đường đi ngắn nhất giữa đỉnh $i$ và $j$ đồng dư với $B_{i,j} \pmod 5$ hay không. Nếu tồn tại một đồ thị như vậy, hãy xuất ra bất kỳ đồ thị khả thi nào.

Dữ liệu vào

Mỗi bài kiểm tra chứa nhiều bộ dữ liệu. Dòng đầu tiên chứa một số nguyên duy nhất $t$ ($1 \le t \le 100$): số lượng bộ dữ liệu. Mô tả các bộ dữ liệu theo sau.

Dòng đầu tiên của mỗi bộ dữ liệu chứa một số nguyên dương $N$.

Sau đó, $N - 1$ dòng tiếp theo sẽ theo sau. Dòng thứ $i$ trong số này sẽ chứa $N - i$ số nguyên dương cách nhau bởi dấu cách. Số nguyên thứ $j$ trên dòng thứ $i$ đại diện cho $B_{i,j+i}$.

Đảm bảo rằng tổng $N$ trên tất cả các bộ dữ liệu không quá 500.

Dữ liệu ra

Với mỗi bộ dữ liệu, hãy xuất "YES" nếu tồn tại một đồ thị khả thi, hoặc "NO" nếu không tồn tại đồ thị như vậy. Bạn có thể xuất câu trả lời ở bất kỳ định dạng chữ hoa hay chữ thường nào. Ví dụ, các chuỗi "yEs", "yes", "Yes", và "YES" đều sẽ được công nhận là phản hồi khẳng định.

Nếu chương trình của bạn trả lời "YES", hãy xuất thêm $N - 1$ dòng. Dòng thứ $i$ trong số này nên chứa $N - i$ số nguyên dương. Số nguyên thứ $j$ trên dòng thứ $i$ là 1 nếu nên có một cạnh giữa đỉnh $i$ và đỉnh $i + j$, và 0 nếu ngược lại.

Nhiệm vụ con

Bạn sẽ nhận được 25% số điểm cho mỗi nhiệm vụ con nếu phản hồi YES/NO là chính xác, nhưng đồ thị được cung cấp không chính xác. Với mỗi bộ dữ liệu có câu trả lời "YES", bạn phải xuất chính xác $N - 1$ dòng với dòng thứ $i$ chứa $N - i$ số nguyên (là 0 hoặc 1) để nhận điểm một phần.

• (20 điểm): Tổng $N$ trên tất cả các bộ dữ liệu không vượt quá 10.
• (80 điểm): Không có ràng buộc bổ sung.

Ví dụ

Dữ liệu vào 1

3
3
1 1
1
3
2 1
1
3
0 0
0

Dữ liệu ra 1

YES
1 1
1
YES
0 1
1
NO

Ghi chú

Trong bộ dữ liệu đầu tiên, có 3 đỉnh và khoảng cách ngắn nhất giữa bất kỳ cặp đỉnh nào là 1 (mod 5). Điều này có thể đạt được bằng cách xây dựng một đồ thị với 3 đỉnh và một cạnh giữa bất kỳ cặp đỉnh nào.

Trong bộ dữ liệu thứ hai, có 3 đỉnh và khoảng cách ngắn nhất giữa đỉnh 1 và 2 là 2 (mod 5), và khoảng cách ngắn nhất giữa đỉnh 1 và 3 cũng như giữa đỉnh 2 và 3 đều là 1 (mod 5). Điều này có thể đạt được bằng cách xây dựng một đồ thị với 3 đỉnh và một cạnh giữa đỉnh 1 và 3 cũng như giữa đỉnh 2 và 3.

Trong bộ dữ liệu thứ ba, có 3 đỉnh và khoảng cách ngắn nhất giữa bất kỳ cặp đỉnh nào là 0 (mod 5). Có thể chứng minh rằng không có đồ thị không trọng số, vô hướng, liên thông nào có thể thỏa mãn bộ dữ liệu này.