Танд $n × n$ хэмжээтэй $A$ матриц өгөгдсөн.

Хэрвээ матриц нь сөрөг биш элементүүдтэй ба бүх $i, j, k$ гурвалын хувьд тэгш хэмтэй (буюу $a_{ij} = a_{ji}$), $a_{ii} = 0$ and $a_{ij} ≤ max(a_{ik}, a_{jk})$ байвал энэ матрицыг шидэт матриц гэнэ.

Матрицыг шидэт мөн эсэхийг тодорхойл.

Оролт гаралт нь маш их хэмжээтэй байж болох тул оролт гаралтын хурдан функцүүдийг ашиглана уу. Жишээ нь: C++ хэлэнд "cin/cout"-ийн оронд "scanf/printf"-ийг ашиглах, $Java$ хэлэнд "Scanner/System.out"-ийн оронд "BufferedReader/PrintWriter"-ийг ашиглана уу.

Оролт

Эхний мөрөнд бүхэл тоон утга $n$ ($1 ≤ n ≤ 2500$) байх ба энэ нь $A$ матрицын хэмжээ юм.

Дараагийн $n$ ширхэг мөр бүрт $n$ ширхэг бүхэл тоон утга $a_{ij}$ ($0 ≤ a_{ij} < 10^{9}$) байх ба $A$ матрицын элементүүд юм.

Өгөгдсөн матриц нь заавал тэгш хэмтэй байх албагүй ба санамсаргүйгээр үүсгэгдсэн ч байж болно.

Гаралт

Хэрвээ өгөгдсөн матриц $A$ нь шидэт матриц байвал "MAGIC" гэж хэвлэ. Бусад тохиолдолд "NOT MAGIC" гэж хэвлэ.