#include <bits/stdc++.h>
using namespace std;
namespace Input {
inline char Sc() {
  static const int LEN = 100000;
  static char Buf[LEN], *OP = Buf, *ED = Buf;
  if (OP == ED) {
    ED = (OP = Buf) + fread(Buf, 1, LEN, stdin);
    if (OP == ED) return -1;
  }
  return *OP++;
}
template <class T>
inline void rd(T &x) {
  static char c;
  for (x = 0, c = Sc(); c < 48; c = Sc())
    if (!~c) {
      x = -1;
      return;
    }
  for (; c > 47; c = Sc()) x = (x << 1) + (x << 3) + (c ^ 48);
}
inline void rd(char *s) {
  static int c, h;
  h = 0;
  for (c = Sc(); c < 33; c = Sc())
    if (!~c) {
      s[0] = 0;
      return;
    }
  for (; c > 32; c = Sc()) s[h++] = c;
  s[h] = 0;
}
}  // namespace Input
using namespace Input;
struct edge {
  int nxt, t, s;
} e[2510 << 1];
int head[2510], edge_cnt;
void add_edge(int x, int y, int z) {
  e[edge_cnt] = (edge){head[x], y, z};
  head[x] = edge_cnt++;
}
int A[2510][2510], d[2510], fa[2510], cur;
bool mark[2510];
void dfs(int x, int f, int Mx) {
  if (Mx != A[cur][x]) {
    printf("NOT MAGIC\n");
    exit(0);
  }
  int i;
  for (i = head[x]; ~i; i = e[i].nxt) {
    int to = e[i].t;
    if (to == f) {
      continue;
    }
    dfs(to, x, max(Mx, e[i].s));
  }
}
int main() {
  int n, i, j;
  rd(n);
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      rd(A[i][j]);
    }
  }
  for (i = 1; i <= n; i++) {
    if (A[i][i] > 0) {
      printf("NOT MAGIC\n");
      exit(0);
    }
    for (j = 1; j <= n; j++) {
      if (A[i][j] != A[j][i]) {
        printf("NOT MAGIC\n");
        exit(0);
      }
    }
  }
  memset(d + 1, 63, sizeof(int) * 1 * n);
  d[1] = 0;
  for (i = 1; i <= n; i++) {
    int Mn = (0x3f3f3f3f), pos = 0;
    for (j = 1; j <= n; j++) {
      if (!mark[j] && d[j] < Mn) {
        Mn = d[j];
        pos = j;
      }
    }
    mark[pos] = 1;
    for (j = 1; j <= n; j++) {
      if (!mark[j] && d[j] > A[pos][j]) {
        d[j] = A[pos][j];
        fa[j] = pos;
      }
    }
  }
  memset(head + 1, -1, sizeof(int) * 1 * n);
  for (i = 2; i <= n; i++) {
    add_edge(fa[i], i, A[fa[i]][i]);
    add_edge(i, fa[i], A[fa[i]][i]);
  }
  for (i = 1; i <= n; i++) {
    cur = i;
    dfs(i, 0, 0);
  }
  printf("MAGIC\n");
  return 0;
}

### Prompt

In CPP, your task is to solve the following problem:

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

Let's call the matrix with nonnegative elements magic if it is symmetric (so aij = aji), aii = 0 and aij ≤ max(aik, ajk) 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.

Input

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

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

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

Output

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

Examples

Input

3
0 1 2
1 0 2
2 2 0


Output

MAGIC


Input

2
0 1
2 3


Output

NOT MAGIC


Input

4
0 1 2 3
1 0 3 4
2 3 0 5
3 4 5 0


Output

NOT MAGIC

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
namespace Input {
inline char Sc() {
  static const int LEN = 100000;
  static char Buf[LEN], *OP = Buf, *ED = Buf;
  if (OP == ED) {
    ED = (OP = Buf) + fread(Buf, 1, LEN, stdin);
    if (OP == ED) return -1;
  }
  return *OP++;
}
template <class T>
inline void rd(T &x) {
  static char c;
  for (x = 0, c = Sc(); c < 48; c = Sc())
    if (!~c) {
      x = -1;
      return;
    }
  for (; c > 47; c = Sc()) x = (x << 1) + (x << 3) + (c ^ 48);
}
inline void rd(char *s) {
  static int c, h;
  h = 0;
  for (c = Sc(); c < 33; c = Sc())
    if (!~c) {
      s[0] = 0;
      return;
    }
  for (; c > 32; c = Sc()) s[h++] = c;
  s[h] = 0;
}
}  // namespace Input
using namespace Input;
struct edge {
  int nxt, t, s;
} e[2510 << 1];
int head[2510], edge_cnt;
void add_edge(int x, int y, int z) {
  e[edge_cnt] = (edge){head[x], y, z};
  head[x] = edge_cnt++;
}
int A[2510][2510], d[2510], fa[2510], cur;
bool mark[2510];
void dfs(int x, int f, int Mx) {
  if (Mx != A[cur][x]) {
    printf("NOT MAGIC\n");
    exit(0);
  }
  int i;
  for (i = head[x]; ~i; i = e[i].nxt) {
    int to = e[i].t;
    if (to == f) {
      continue;
    }
    dfs(to, x, max(Mx, e[i].s));
  }
}
int main() {
  int n, i, j;
  rd(n);
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      rd(A[i][j]);
    }
  }
  for (i = 1; i <= n; i++) {
    if (A[i][i] > 0) {
      printf("NOT MAGIC\n");
      exit(0);
    }
    for (j = 1; j <= n; j++) {
      if (A[i][j] != A[j][i]) {
        printf("NOT MAGIC\n");
        exit(0);
      }
    }
  }
  memset(d + 1, 63, sizeof(int) * 1 * n);
  d[1] = 0;
  for (i = 1; i <= n; i++) {
    int Mn = (0x3f3f3f3f), pos = 0;
    for (j = 1; j <= n; j++) {
      if (!mark[j] && d[j] < Mn) {
        Mn = d[j];
        pos = j;
      }
    }
    mark[pos] = 1;
    for (j = 1; j <= n; j++) {
      if (!mark[j] && d[j] > A[pos][j]) {
        d[j] = A[pos][j];
        fa[j] = pos;
      }
    }
  }
  memset(head + 1, -1, sizeof(int) * 1 * n);
  for (i = 2; i <= n; i++) {
    add_edge(fa[i], i, A[fa[i]][i]);
    add_edge(i, fa[i], A[fa[i]][i]);
  }
  for (i = 1; i <= n; i++) {
    cur = i;
    dfs(i, 0, 0);
  }
  printf("MAGIC\n");
  return 0;
}

```