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
from collections import defaultdict, deque
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def get_root(s):
    v = []
    while not s == root[s]:
        v.append(s)
        s = root[s]
    for i in v:
        root[i] = s
    return s

def unite(s, t):
    rs, rt = get_root(s), get_root(t)
    if not rs ^ rt:
        return
    if rank[s] == rank[t]:
        rank[rs] += 1
    if rank[s] >= rank[t]:
        root[rt] = rs
        size[rs] += size[rt]
    else:
        root[rs] = rt
        size[rt] += size[rs]
    return

def same(s, t):
    return True if get_root(s) == get_root(t) else False

def bfs(s):
    q = deque()
    q.append(s)
    dist = [-1] * n
    dist[s] = 0
    while q:
        i = q.popleft()
        di = dist[i]
        for j, c in G[i]:
            if dist[j] == -1:
                dist[j] = max(di, c)
                q.append(j)
    return dist

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
d = defaultdict(lambda : [])
ok = 1
for i in range(n):
    ai = a[i]
    for j in range(i + 1, n):
        if ai[j] ^ a[j][i]:
            ok = 0
            break
        d[ai[j]].append(i * n + j)
    if ai[i]:
        ok = 0
    if not ok:
        break
if ok:
    root = [i for i in range(n)]
    rank = [1 for _ in range(n)]
    size = [1 for _ in range(n)]
    G = [[] for _ in range(n)]
    c = 1
    for i in sorted(d.keys()):
        for x in d[i]:
            u, v = x // n, x % n
            if not same(u, v):
                unite(u, v)
                auv = a[u][v]
                G[u].append((v, auv))
                G[v].append((u, auv))
                c += 1
            if not c ^ n:
                break
        if not c ^ n:
            break
    for i in range(n):
        dist = bfs(i)
        ai = a[i]
        for x, y in zip(dist, ai):
            if x < y:
                ok = 0
                break
        if not ok:
            break
ans = "MAGIC" if ok else "NOT MAGIC"
print(ans)