#include <bits/stdc++.h>
using namespace std;
int N, L;
int a[2505][2505], up[2505][20], DP[2505][20], tin[2505], tout[2505],
    timmer = 0;
vector<array<int, 2>> mst[2505];
int fa[2505];
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void merge(int x, int y) {
  x = find(x);
  y = find(y);
  fa[x] = y;
}
void DFS(int v, int p, int cost) {
  tin[v] = ++timmer;
  up[v][0] = p;
  DP[v][0] = cost;
  for (int i = 1; i <= L; ++i) {
    up[v][i] = up[up[v][i - 1]][i - 1];
    DP[v][i] = max(DP[v][i - 1], DP[up[v][i - 1]][i - 1]);
  }
  for (auto& e : mst[v]) {
    int nv = e[0], w = e[1];
    if (nv == p) continue;
    DFS(nv, v, w);
  }
  tout[v] = ++timmer;
}
bool isAncestor(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }
int getmax(int v, int u) {
  int ans = 0;
  if (tin[v] >= tin[u]) swap(u, v);
  if (isAncestor(v, u)) {
    for (int i = L; i >= 0; --i) {
      if (!isAncestor(up[u][i], v)) {
        ans = max(ans, DP[u][i]);
        u = up[u][i];
      }
    }
    ans = max(ans, DP[u][0]);
  } else {
    int x = u, y = v;
    for (int i = L; i >= 0; --i) {
      if (!isAncestor(up[x][i], v)) {
        ans = max(ans, DP[x][i]);
        x = up[x][i];
      }
    }
    ans = max(ans, DP[x][0]);
    for (int i = L; i >= 0; --i) {
      if (!isAncestor(up[y][i], u)) {
        ans = max(ans, DP[y][i]);
        y = up[y][i];
      }
    }
    ans = max(ans, DP[y][0]);
  }
  return ans;
}
int main() {
  scanf("%d", &N);
  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= N; ++j) {
      scanf("%d", &a[i][j]);
    }
  }
  int ok = 1;
  for (int i = 1; i <= N; ++i)
    if (a[i][i] != 0) ok = 0;
  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= N; ++j) {
      if (a[i][j] != a[j][i]) ok = 0;
    }
  }
  if (!ok) {
    printf("NOT MAGIC\n");
    return 0;
  }
  vector<array<int, 3>> edges;
  for (int i = 1; i <= N; ++i) {
    for (int j = i + 1; j <= N; ++j) {
      edges.push_back({a[i][j], i, j});
    }
  }
  sort(edges.begin(), edges.end());
  for (int i = 1; i <= N; ++i) fa[i] = i;
  for (auto& e : edges) {
    int x = e[1], y = e[2];
    if (find(x) != find(y)) {
      mst[x].push_back({y, e[0]});
      mst[y].push_back({x, e[0]});
      merge(x, y);
    }
  }
  L = ceil(log2(N));
  DFS(1, 1, 0);
  for (int i = 1; i <= N; ++i) {
    for (int j = i + 1; j <= N; ++j) {
      if (a[i][j] > getmax(i, j)) {
        printf("NOT MAGIC\n");
        return 0;
      }
    }
  }
  printf("MAGIC\n");
}

### 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 N, L;
int a[2505][2505], up[2505][20], DP[2505][20], tin[2505], tout[2505],
    timmer = 0;
vector<array<int, 2>> mst[2505];
int fa[2505];
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void merge(int x, int y) {
  x = find(x);
  y = find(y);
  fa[x] = y;
}
void DFS(int v, int p, int cost) {
  tin[v] = ++timmer;
  up[v][0] = p;
  DP[v][0] = cost;
  for (int i = 1; i <= L; ++i) {
    up[v][i] = up[up[v][i - 1]][i - 1];
    DP[v][i] = max(DP[v][i - 1], DP[up[v][i - 1]][i - 1]);
  }
  for (auto& e : mst[v]) {
    int nv = e[0], w = e[1];
    if (nv == p) continue;
    DFS(nv, v, w);
  }
  tout[v] = ++timmer;
}
bool isAncestor(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }
int getmax(int v, int u) {
  int ans = 0;
  if (tin[v] >= tin[u]) swap(u, v);
  if (isAncestor(v, u)) {
    for (int i = L; i >= 0; --i) {
      if (!isAncestor(up[u][i], v)) {
        ans = max(ans, DP[u][i]);
        u = up[u][i];
      }
    }
    ans = max(ans, DP[u][0]);
  } else {
    int x = u, y = v;
    for (int i = L; i >= 0; --i) {
      if (!isAncestor(up[x][i], v)) {
        ans = max(ans, DP[x][i]);
        x = up[x][i];
      }
    }
    ans = max(ans, DP[x][0]);
    for (int i = L; i >= 0; --i) {
      if (!isAncestor(up[y][i], u)) {
        ans = max(ans, DP[y][i]);
        y = up[y][i];
      }
    }
    ans = max(ans, DP[y][0]);
  }
  return ans;
}
int main() {
  scanf("%d", &N);
  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= N; ++j) {
      scanf("%d", &a[i][j]);
    }
  }
  int ok = 1;
  for (int i = 1; i <= N; ++i)
    if (a[i][i] != 0) ok = 0;
  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= N; ++j) {
      if (a[i][j] != a[j][i]) ok = 0;
    }
  }
  if (!ok) {
    printf("NOT MAGIC\n");
    return 0;
  }
  vector<array<int, 3>> edges;
  for (int i = 1; i <= N; ++i) {
    for (int j = i + 1; j <= N; ++j) {
      edges.push_back({a[i][j], i, j});
    }
  }
  sort(edges.begin(), edges.end());
  for (int i = 1; i <= N; ++i) fa[i] = i;
  for (auto& e : edges) {
    int x = e[1], y = e[2];
    if (find(x) != find(y)) {
      mst[x].push_back({y, e[0]});
      mst[y].push_back({x, e[0]});
      merge(x, y);
    }
  }
  L = ceil(log2(N));
  DFS(1, 1, 0);
  for (int i = 1; i <= N; ++i) {
    for (int j = i + 1; j <= N; ++j) {
      if (a[i][j] > getmax(i, j)) {
        printf("NOT MAGIC\n");
        return 0;
      }
    }
  }
  printf("MAGIC\n");
}

```