CF632F.Magic Matrix

You're given a matrix A of size n × n.

Let's call the matrix with nonnegative elements magic if it is symmetric (so a__ij = a__ji), a__ii = 0 and a__ij ≤ max(a__ik, a__jk) for all triples i, j, k. Note that i, j, k do not need to be distinct.

Determine if the matrix is magic.

As the input/output can reach very huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

给你一个大小为 $n \times n$ 的矩阵 $A$。

我们称一个所有元素均为非负数的矩阵为魔法矩阵，当且仅当它满足以下条件：

• 对称（即对所有 $i,j$ 有 $a_{ij} = a_{ji}$）；
• 所有对角线元素为零（即对所有 $i$ 有 $a_{ii} = 0$）；
• 对任意三元组 $i, j, k$（$i, j, k$ 可以不互异），均有 $a_{ij} \le \max(a_{ik},\, a_{jk})$。

请判断给定矩阵是否为魔法矩阵。

由于输入/输出规模可能极大，建议使用快速输入/输出方式：例如，在 C++ 中优先使用 scanf/printf 而非 cin/cout；在 Java 中优先使用 BufferedReader/PrintWriter 而非 Scanner/System.out。

The first line contains integer n (1 ≤ n ≤ 2500) — the size of the matrix A.

Each of the next n lines contains n integers a__ij (0 ≤ a__ij < 109) — the elements of the matrix A.

Note that the given matrix not necessarily is symmetric and can be arbitrary.

第一行包含一个整数 $n$（$1 \leq n \leq 2500$）——矩阵 $A$ 的大小。

接下来的 $n$ 行，每行包含 $n$ 个整数 $a_{ij}$（$0 \leq a_{ij} < 10^9$）——矩阵 $A$ 的元素。

注意：给定的矩阵不一定对称，可以是任意矩阵。

Print ''MAGIC" (without quotes) if the given matrix A is magic. Otherwise print ''NOT MAGIC".

如果给定矩阵 $A$ 是幻方，则输出 MAGIC''（不带引号）；否则输出 NOT MAGIC''。