#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x) {
  char ch;
  int f = 1;
  while (ch = getchar(), ch > '9' || ch < '0') (ch == '-') && (f = -1);
  x = (ch ^ 48);
  while (ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48);
  x *= f;
}
template <typename T>
inline void write(T x) {
  static int stk[100], top = 0;
  if (x == 0) return (void)putchar('0');
  if (x < 0) x = -x, putchar('-');
  while (x) stk[++top] = x % 10, x /= 10;
  while (top) putchar(stk[top--] + '0');
}
const int N = 2.5e3 + 10;
int n, a[N][N];
namespace Prim {
int fa[N], minE[N], dis[N][N];
bool vis[N];
bool check() {
  memset(dis, 0x3f, sizeof(dis));
  vis[1] = true;
  for (int i = 1; i <= n; ++i) minE[i] = a[1][i], fa[i] = 1, dis[i][i] = 0;
  for (int i = 1, x; i < n; ++i) {
    x = 0;
    for (int j = 1; j <= n; ++j) {
      if (!vis[j] && (!x || minE[j] < minE[x])) x = j;
    }
    vis[x] = true;
    for (int y = 1; y <= n; ++y) {
      if (!vis[y]) {
        if (minE[y] > a[x][y]) {
          minE[y] = a[x][y], fa[y] = x;
        }
      } else {
        dis[y][x] = dis[x][y] = min(dis[x][y], max(minE[x], dis[y][fa[x]]));
        if (dis[x][y] < a[x][y]) {
          return false;
        }
      }
    }
  }
  return true;
}
}  // namespace Prim
namespace Kruskal {
struct UF {
  int fa[N];
  UF() {
    for (int i = 1; i < N; ++i) fa[i] = i;
  }
  int Find(int x) { return x == fa[x] ? x : fa[x] = Find(fa[x]); }
  void Union(int x, int y) { fa[Find(x)] = Find(y); }
} UF;
struct E {
  int x, y, w;
  E() {}
  E(int X, int Y, int W) : x(X), y(Y), w(W) {}
  bool operator<(const E &rhs) const { return w < rhs.w; }
} e[N * N];
bool check() {
  int cnt = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (i != j) e[++cnt] = E(i, j, a[i][j]);
    }
  }
  sort(e + 1, e + cnt + 1);
  for (int l = 1, r = 0; l <= cnt; l = r + 1) {
    while (r < cnt && e[r + 1].w == e[l].w) ++r;
    for (int i = l; i <= r; ++i) {
      if (UF.Find(e[i].x) == UF.Find(e[i].y)) {
        return false;
      }
    }
    for (int i = l; i <= r; ++i) UF.Union(e[i].x, e[i].y);
  }
  return true;
}
}  // namespace Kruskal
int main() {
  read(n);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      read(a[i][j]);
    }
  }
  for (int i = 1; i <= n; ++i)
    if (a[i][i]) puts("NOT MAGIC"), exit(0);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j < i; ++j) {
      if (a[i][j] ^ a[j][i]) puts("NOT MAGIC"), exit(0);
    }
  }
  puts(Kruskal::check() ? "MAGIC" : "NOT MAGIC");
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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;
template <typename T>
inline void read(T &x) {
  char ch;
  int f = 1;
  while (ch = getchar(), ch > '9' || ch < '0') (ch == '-') && (f = -1);
  x = (ch ^ 48);
  while (ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48);
  x *= f;
}
template <typename T>
inline void write(T x) {
  static int stk[100], top = 0;
  if (x == 0) return (void)putchar('0');
  if (x < 0) x = -x, putchar('-');
  while (x) stk[++top] = x % 10, x /= 10;
  while (top) putchar(stk[top--] + '0');
}
const int N = 2.5e3 + 10;
int n, a[N][N];
namespace Prim {
int fa[N], minE[N], dis[N][N];
bool vis[N];
bool check() {
  memset(dis, 0x3f, sizeof(dis));
  vis[1] = true;
  for (int i = 1; i <= n; ++i) minE[i] = a[1][i], fa[i] = 1, dis[i][i] = 0;
  for (int i = 1, x; i < n; ++i) {
    x = 0;
    for (int j = 1; j <= n; ++j) {
      if (!vis[j] && (!x || minE[j] < minE[x])) x = j;
    }
    vis[x] = true;
    for (int y = 1; y <= n; ++y) {
      if (!vis[y]) {
        if (minE[y] > a[x][y]) {
          minE[y] = a[x][y], fa[y] = x;
        }
      } else {
        dis[y][x] = dis[x][y] = min(dis[x][y], max(minE[x], dis[y][fa[x]]));
        if (dis[x][y] < a[x][y]) {
          return false;
        }
      }
    }
  }
  return true;
}
}  // namespace Prim
namespace Kruskal {
struct UF {
  int fa[N];
  UF() {
    for (int i = 1; i < N; ++i) fa[i] = i;
  }
  int Find(int x) { return x == fa[x] ? x : fa[x] = Find(fa[x]); }
  void Union(int x, int y) { fa[Find(x)] = Find(y); }
} UF;
struct E {
  int x, y, w;
  E() {}
  E(int X, int Y, int W) : x(X), y(Y), w(W) {}
  bool operator<(const E &rhs) const { return w < rhs.w; }
} e[N * N];
bool check() {
  int cnt = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (i != j) e[++cnt] = E(i, j, a[i][j]);
    }
  }
  sort(e + 1, e + cnt + 1);
  for (int l = 1, r = 0; l <= cnt; l = r + 1) {
    while (r < cnt && e[r + 1].w == e[l].w) ++r;
    for (int i = l; i <= r; ++i) {
      if (UF.Find(e[i].x) == UF.Find(e[i].y)) {
        return false;
      }
    }
    for (int i = l; i <= r; ++i) UF.Union(e[i].x, e[i].y);
  }
  return true;
}
}  // namespace Kruskal
int main() {
  read(n);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      read(a[i][j]);
    }
  }
  for (int i = 1; i <= n; ++i)
    if (a[i][i]) puts("NOT MAGIC"), exit(0);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j < i; ++j) {
      if (a[i][j] ^ a[j][i]) puts("NOT MAGIC"), exit(0);
    }
  }
  puts(Kruskal::check() ? "MAGIC" : "NOT MAGIC");
  return 0;
}

```