#include <bits/stdc++.h>
using namespace std;
int a[2500][2500];
int s[2500][2500];
int used[2500];
int min_edg[2500];
int f[2500];
int main() {
  int q, w, e, r, t;
  scanf("%d", &q);
  for (e = 0; e < q; e++) {
    used[e] = 0;
    min_edg[e] = 1 << 30;
    for (r = 0; r < q; r++) {
      scanf("%d", &a[e][r]);
      s[e][r] = 1 << 30;
    }
    s[e][e] = 0;
  }
  for (e = 0; e < q; e++) {
    if (a[e][e] != 0) {
      cout << "NOT MAGIC";
      return 0;
    }
    for (r = 0; r < q; r++) {
      if (a[e][r] != a[r][e]) {
        cout << "NOT MAGIC";
        return 0;
      }
    }
  }
  used[0] = 1;
  for (w = 0; w < q; w++) {
    min_edg[w] = min(min_edg[w], a[0][w]);
    f[w] = 0;
  }
  while (1) {
    r = -1;
    for (e = 0; e < q; e++) {
      if ((!used[e]) && ((r == -1) || (min_edg[e] < min_edg[r]))) {
        r = e;
      }
    }
    if (r == -1) {
      break;
    }
    used[r] = 1;
    for (w = 0; w < q; w++) {
      if (used[w]) {
        s[r][w] = s[w][r] = min(s[w][r], max(s[w][f[r]], min_edg[r]));
        if (s[w][r] < a[w][r]) {
          cout << "NOT MAGIC";
          return 0;
        }
      } else {
        if (min_edg[w] > a[r][w]) {
          min_edg[w] = a[r][w];
          f[w] = r;
        }
      }
    }
  }
  cout << "MAGIC";
  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[2500][2500];
int s[2500][2500];
int used[2500];
int min_edg[2500];
int f[2500];
int main() {
  int q, w, e, r, t;
  scanf("%d", &q);
  for (e = 0; e < q; e++) {
    used[e] = 0;
    min_edg[e] = 1 << 30;
    for (r = 0; r < q; r++) {
      scanf("%d", &a[e][r]);
      s[e][r] = 1 << 30;
    }
    s[e][e] = 0;
  }
  for (e = 0; e < q; e++) {
    if (a[e][e] != 0) {
      cout << "NOT MAGIC";
      return 0;
    }
    for (r = 0; r < q; r++) {
      if (a[e][r] != a[r][e]) {
        cout << "NOT MAGIC";
        return 0;
      }
    }
  }
  used[0] = 1;
  for (w = 0; w < q; w++) {
    min_edg[w] = min(min_edg[w], a[0][w]);
    f[w] = 0;
  }
  while (1) {
    r = -1;
    for (e = 0; e < q; e++) {
      if ((!used[e]) && ((r == -1) || (min_edg[e] < min_edg[r]))) {
        r = e;
      }
    }
    if (r == -1) {
      break;
    }
    used[r] = 1;
    for (w = 0; w < q; w++) {
      if (used[w]) {
        s[r][w] = s[w][r] = min(s[w][r], max(s[w][f[r]], min_edg[r]));
        if (s[w][r] < a[w][r]) {
          cout << "NOT MAGIC";
          return 0;
        }
      } else {
        if (min_edg[w] > a[r][w]) {
          min_edg[w] = a[r][w];
          f[w] = r;
        }
      }
    }
  }
  cout << "MAGIC";
  return 0;
}

```