Ma trận kỳ diệu

Cho một ma trận vuông $A$ kích thước $n\times n$ với các phần tử không âm.

Ma trận được gọi là kỳ diệu nếu nó thỏa mãn đồng thời tất cả các điều kiện sau:

• Đối xứng: $a_{ij}=a_{ji}$ với mọi $i,j$.
• Đường chéo bằng $0$: $a_{ii}=0$ với mọi $i$.
• Với mọi bộ ba chỉ số $i,j,k$ (các chỉ số không nhất thiết phân biệt): $a_{ij}\le max(a_{ik},a_{jk})$.

Ma trận đầu vào không nhất thiết đối xứng và có thể tùy ý. Hãy xác định xem ma trận đã cho có kỳ diệu hay không.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$ là kích thước của ma trận $A$.
• $n$ dòng tiếp theo, mỗi dòng chứa $n$ số nguyên $a_{ij}$ là các phần tử của ma trận.

Dữ liệu ra

In ra MAGIC nếu ma trận là kỳ diệu, ngược lại in ra NOT MAGIC.

Ràng buộc

• $1\le n\le 2500$
• $0\le a_{ij}<{10}^9$

Ví dụ