给定一个大小为 n × n 的矩阵 A。
如果具有非负元素的矩阵是对称的(因此 aij = aji)、aii = 0 且对于所有三元组 i、j、k,aij ≤ max(aik, ajk),我们将其称为 magic。请注意,i、j、k 不需要不同。
确定矩阵是否是魔法矩阵。
由于输入/输出可能达到非常大的尺寸,建议使用快速输入/输出方法:例如,在C++中更喜欢使用scanf/printf而不是cin/cout,在Java中更喜欢使用BufferedReader/PrintWriter而不是Scanner/System.out。
输入
第一行包含整数 n (1 ≤ n ≤ 2500) — 矩阵 A 的大小。
接下来的 n 行中的每一行都包含 n 个整数 aij (0 ≤ aij < 109) — 矩阵 A 的元素。
请注意,给定的矩阵不一定是对称的,并且可以是任意的。
输出
如果给定矩阵 A 是 magic,则打印“MAGIC”(不带引号)。否则打印“NOT MAGIC”。
示例
输入 #1
3 0 1 2 1 0 2 2 2 0
输出 #1
MAGIC
输入 #2
2 0 1 2 3
输出 #2
NOT MAGIC
输入 #3
4 0 1 2 3 1 0 3 4 2 3 0 5 3 4 5 0
输出 #3
NOT MAGIC