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*<sub class="lower-index">*ij*</sub> = *a*<sub class="lower-index">*ji*</sub>), *a*<sub class="lower-index">*ii*</sub> = 0 and *a*<sub class="lower-index">*ij*</sub> ≤ *max*(*a*<sub class="lower-index">*ik*</sub>, *a*<sub class="lower-index">*jk*</sub>) 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.
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*<sub class="lower-index">*ij*</sub> (0 ≤ *a*<sub class="lower-index">*ij*</sub> &lt; 10<sup class="upper-index">9</sup>) — the elements of the matrix *A*.

Note that the given matrix not necessarily is symmetric and can be arbitrary.
none
3
0 1 2
1 0 2
2 2 0
MAGIC
2
0 1
2 3
NOT MAGIC
4
0 1 2 3
1 0 3 4
2 3 0 5
3 4 5 0
NOT MAGIC
5
0 2 5 9 5
2 0 5 9 5
5 5 0 9 4
9 9 9 0 9
5 5 4 9 0
MAGIC
10
0 16 5 14 14 17 14 14 9 14
16 0 16 16 16 17 16 16 16 16
5 16 0 14 14 17 14 14 9 14
14 16 14 0 7 17 3 8 14 12
14 16 14 7 0 17 7 8 14 12
17 17 17 17 17 0 17 17 17 17
14 16 14 3 7 17 0 8 14 12
14 16 14 8 8 17 8 0 14 12
9 16 9 14 14 17 14 14 0 14
14 16 14 12 12 17 12 12 14 0
MAGIC
5
0 2 9 10 10
2 0 5 2 3
9 5 0 1 1
10 2 1 0 7
10 3 1 7 0
NOT MAGIC
10
0 18 0 12 20 3 14 12 13 2
18 0 6 12 7 20 1 9 13 10
0 6 0 15 17 9 16 15 1 0
12 12 15 0 0 8 19 20 11 11
20 7 17 0 0 3 5 14 8 3
3 20 9 8 3 0 7 16 20 17
14 1 16 19 5 7 0 14 18 14
12 9 15 20 14 16 14 0 6 19
13 13 1 11 8 20 18 6 0 13
2 10 0 11 3 17 14 19 13 0
NOT MAGIC
2
1 1
1 1
NOT MAGIC
3
0 999999998 999999998
999999998 0 999999999
999999998 999999999 0
NOT MAGIC
5
0 3 7 1 1
3 0 7 1 1
7 7 0 7 7
1 1 7 0 1
1 1 7 1 0
NOT MAGIC
5
0 2 9 1 1
2 0 9 1 1
9 9 0 9 9
1 1 9 0 1
1 1 9 1 0
NOT MAGIC
3
0 1 2
0 0 2
2 2 0
NOT MAGIC
3
1 2 3
2 1 3
3 3 1
NOT MAGIC
4
0 9 9 9
9 0 1 2
9 1 0 3
9 2 3 0
NOT MAGIC
2
2 2
2 2
NOT MAGIC
4
0 1 2 9
1 0 3 9
2 3 0 9
9 9 9 0
NOT MAGIC
4
0 0 0 4
0 0 3 4
0 3 0 4
4 4 4 0
NOT MAGIC
import sys
def input(): return sys.stdin.readline().strip()

n = int(input())

l = [0]*n
for x in range(n): l[x] = tuple(input().split())

l2 = list(zip(*l))

for x in range(n):
    if l[x] != l2[x]:
        print("NOT MAGIC")
        break
else: print("MAGIC")

