#include <bits/stdc++.h>
using namespace std;
int a[2505][2505];
struct node {
  int len, l, r;
} e[2505 * 2505 / 2];
int pre[2505], ran[2505], num[2505], maxx[2505];
struct edg {
  int next, to, len;
} edge[2 * 2505];
int first[2505];
int findset(int x) {
  int i, j = x, r = x;
  while (r != pre[r]) r = pre[r];
  while (j != pre[j]) {
    i = pre[j];
    pre[j] = r;
    j = i;
  }
  return r;
}
bool cmp(node a, node b) { return a.len < b.len; }
int flag;
void dfs(int u, int father, int x) {
  int i, j, v;
  for (i = first[u]; i != -1; i = edge[i].next) {
    v = edge[i].to;
    if (v == father) continue;
    maxx[v] = max(maxx[u], edge[i].len);
    if (a[x][v] != maxx[v]) {
      flag = 0;
      break;
    }
    dfs(v, u, x);
    if (flag == 0) break;
  }
}
int main() {
  int n, m, i, j;
  while (scanf("%d", &n) != EOF) {
    flag = 1;
    int tot = 0;
    for (i = 1; i <= n; i++) {
      pre[i] = i;
      ran[i] = 0;
      num[i] = 1;
      for (j = 1; j <= n; j++) {
        scanf("%d", &a[i][j]);
        if (i < j) {
          tot++;
          e[tot].len = a[i][j];
          e[tot].l = i;
          e[tot].r = j;
        }
      }
    }
    for (i = 1; i <= n; i++) {
      if (a[i][i] != 0) {
        flag = 0;
        break;
      }
    }
    if (flag == 0) {
      printf("NOT MAGIC\n");
      continue;
    }
    for (i = 1; i <= n; i++) {
      for (j = i + 1; j <= n; j++) {
        if (a[i][j] != a[j][i]) {
          flag = 0;
          break;
        }
      }
      if (!flag) break;
    }
    if (flag == 0) {
      printf("NOT MAGIC\n");
      continue;
    }
    sort(e + 1, e + 1 + tot, cmp);
    int t1, t2, u, v, x, y;
    int t = 0;
    memset(first, -1, sizeof(first));
    for (i = 1; i <= tot; i++) {
      u = e[i].l;
      v = e[i].r;
      x = findset(u);
      y = findset(v);
      if (x == y) continue;
      t++;
      edge[t].next = first[u];
      edge[t].to = v;
      edge[t].len = a[u][v];
      first[u] = t;
      t++;
      edge[t].next = first[v];
      edge[t].to = u;
      edge[t].len = a[u][v];
      first[v] = t;
      if (ran[x] > ran[y]) {
        pre[y] = x;
        num[x] += num[y];
        if (num[x] == n) break;
      } else {
        pre[x] = y;
        num[y] += num[x];
        if (num[y] == n) break;
        if (ran[x] == ran[y]) ran[y]++;
      }
    }
    for (j = 1; j <= n; j++) {
      maxx[j] = 0;
      dfs(j, 0, j);
      if (flag == 0) break;
    }
    if (flag)
      printf("MAGIC\n");
    else
      printf("NOT MAGIC\n");
  }
  return 0;
}

### Prompt

Please formulate a Cpp solution to 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;
int a[2505][2505];
struct node {
  int len, l, r;
} e[2505 * 2505 / 2];
int pre[2505], ran[2505], num[2505], maxx[2505];
struct edg {
  int next, to, len;
} edge[2 * 2505];
int first[2505];
int findset(int x) {
  int i, j = x, r = x;
  while (r != pre[r]) r = pre[r];
  while (j != pre[j]) {
    i = pre[j];
    pre[j] = r;
    j = i;
  }
  return r;
}
bool cmp(node a, node b) { return a.len < b.len; }
int flag;
void dfs(int u, int father, int x) {
  int i, j, v;
  for (i = first[u]; i != -1; i = edge[i].next) {
    v = edge[i].to;
    if (v == father) continue;
    maxx[v] = max(maxx[u], edge[i].len);
    if (a[x][v] != maxx[v]) {
      flag = 0;
      break;
    }
    dfs(v, u, x);
    if (flag == 0) break;
  }
}
int main() {
  int n, m, i, j;
  while (scanf("%d", &n) != EOF) {
    flag = 1;
    int tot = 0;
    for (i = 1; i <= n; i++) {
      pre[i] = i;
      ran[i] = 0;
      num[i] = 1;
      for (j = 1; j <= n; j++) {
        scanf("%d", &a[i][j]);
        if (i < j) {
          tot++;
          e[tot].len = a[i][j];
          e[tot].l = i;
          e[tot].r = j;
        }
      }
    }
    for (i = 1; i <= n; i++) {
      if (a[i][i] != 0) {
        flag = 0;
        break;
      }
    }
    if (flag == 0) {
      printf("NOT MAGIC\n");
      continue;
    }
    for (i = 1; i <= n; i++) {
      for (j = i + 1; j <= n; j++) {
        if (a[i][j] != a[j][i]) {
          flag = 0;
          break;
        }
      }
      if (!flag) break;
    }
    if (flag == 0) {
      printf("NOT MAGIC\n");
      continue;
    }
    sort(e + 1, e + 1 + tot, cmp);
    int t1, t2, u, v, x, y;
    int t = 0;
    memset(first, -1, sizeof(first));
    for (i = 1; i <= tot; i++) {
      u = e[i].l;
      v = e[i].r;
      x = findset(u);
      y = findset(v);
      if (x == y) continue;
      t++;
      edge[t].next = first[u];
      edge[t].to = v;
      edge[t].len = a[u][v];
      first[u] = t;
      t++;
      edge[t].next = first[v];
      edge[t].to = u;
      edge[t].len = a[u][v];
      first[v] = t;
      if (ran[x] > ran[y]) {
        pre[y] = x;
        num[x] += num[y];
        if (num[x] == n) break;
      } else {
        pre[x] = y;
        num[y] += num[x];
        if (num[y] == n) break;
        if (ran[x] == ran[y]) ran[y]++;
      }
    }
    for (j = 1; j <= n; j++) {
      maxx[j] = 0;
      dfs(j, 0, j);
      if (flag == 0) break;
    }
    if (flag)
      printf("MAGIC\n");
    else
      printf("NOT MAGIC\n");
  }
  return 0;
}

```