#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T& x) {
  char c;
  bool f = 0;
  while ((c = getchar()) < '0' || '9' < c) f |= (c == '-');
  for (x = (c ^ 48); '0' <= (c = getchar()) && c <= '9';
       x = (x << 1) + (x << 3) + (c ^ 48))
    ;
  if (f) x = -x;
}
template <class T>
inline T read(const T sample) {
  T x = 0;
  char c;
  bool f = 0;
  while ((c = getchar()) < '0' || '9' < c) f |= (c == '-');
  for (x = (c ^ 48); '0' <= (c = getchar()) && c <= '9';
       x = (x << 1) + (x << 3) + (c ^ 48))
    ;
  return f ? -x : x;
}
template <class T>
void fwrit(const T x) {
  if (x < 0) return (void)(putchar('-'), fwrit(-x));
  if (x > 9) fwrit(x / 10);
  putchar(x % 10 ^ 48);
}
template <class T>
inline T Max(const T x, const T y) {
  return x > y ? x : y;
}
template <class T>
inline T Min(const T x, const T y) {
  return x < y ? x : y;
}
template <class T>
inline T fab(const T x) {
  return x > 0 ? x : -x;
}
inline int gcd(const int a, const int b) { return b ? gcd(b, a % b) : a; }
inline void getInv(int inv[], const int lim, const int MOD) {
  inv[0] = inv[1] = 1;
  for (int i = 2; i <= lim; ++i)
    inv[i] = 1ll * inv[MOD % i] * (MOD - MOD / i) % MOD;
}
inline long long mulMod(const long long a, const long long b,
                        const long long mod) {
  return ((a * b - (long long)((long double)a / mod * b + 1e-8) * mod) % mod +
          mod) %
         mod;
}
const int MAXN = 2500;
int n, a[MAXN + 5][MAXN + 5];
pair<int, int> t[MAXN * MAXN + 5];
inline void Init() {
  n = read(1);
  for (signed i = (1), i_end_ = (n); i <= i_end_; ++i)
    for (signed j = (1), j_end_ = (n); j <= j_end_; ++j) a[i][j] = read(1);
}
inline bool cmp(const pair<int, int> i, const pair<int, int> j) {
  return a[i.first][i.second] < a[j.first][j.second];
}
vector<pair<int, int> > pos[MAXN * MAXN + 5];
int hcnt;
inline void hasMatrix() {
  for (signed i = (1), i_end_ = (n); i <= i_end_; ++i)
    for (signed j = (1), j_end_ = (n); j <= j_end_; ++j)
      t[(i - 1) * n + j] = make_pair(i, j);
  sort(t + 1, t + (n * n) + 1, cmp);
  int pre = a[t[1].first][t[1].second], hasnum = 1;
  a[t[1].first][t[1].second] = 1;
  for (signed i = (2), i_end_ = (n * n); i <= i_end_; ++i) {
    hasnum += (a[t[i].first][t[i].second] != pre);
    pos[hasnum].push_back(t[i]);
    pre = a[t[i].first][t[i].second];
    a[t[i].first][t[i].second] = hasnum;
  }
  hcnt = hasnum;
}
bitset<MAXN + 5> x[MAXN + 5], y[MAXN + 5], res;
inline void check() {
  int sz, p, q;
  for (signed i = (1), i_end_ = (hcnt); i <= i_end_; ++i) {
    sz = pos[i].size();
    for (signed j = (0), j_end_ = (sz - 1); j <= j_end_; ++j) {
      p = pos[i][j].first, q = pos[i][j].second;
      res = x[p] & y[q];
      if (res.any()) {
        puts("NOT MAGIC");
        return;
      }
    }
    for (signed j = (0), j_end_ = (sz - 1); j <= j_end_; ++j) {
      p = pos[i][j].first, q = pos[i][j].second;
      x[p][q] = y[q][p] = 1;
    }
  }
  puts("MAGIC");
}
signed main() {
  Init();
  for (signed i = (1), i_end_ = (n); i <= i_end_; ++i)
    for (signed j = (1), j_end_ = (n); j <= j_end_; ++j) {
      if (a[i][j] != a[j][i] || (i == j && a[i][j] != 0)) {
        puts("NOT MAGIC");
        return 0;
      }
    }
  hasMatrix();
  check();
  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;
template <class T>
inline void read(T& x) {
  char c;
  bool f = 0;
  while ((c = getchar()) < '0' || '9' < c) f |= (c == '-');
  for (x = (c ^ 48); '0' <= (c = getchar()) && c <= '9';
       x = (x << 1) + (x << 3) + (c ^ 48))
    ;
  if (f) x = -x;
}
template <class T>
inline T read(const T sample) {
  T x = 0;
  char c;
  bool f = 0;
  while ((c = getchar()) < '0' || '9' < c) f |= (c == '-');
  for (x = (c ^ 48); '0' <= (c = getchar()) && c <= '9';
       x = (x << 1) + (x << 3) + (c ^ 48))
    ;
  return f ? -x : x;
}
template <class T>
void fwrit(const T x) {
  if (x < 0) return (void)(putchar('-'), fwrit(-x));
  if (x > 9) fwrit(x / 10);
  putchar(x % 10 ^ 48);
}
template <class T>
inline T Max(const T x, const T y) {
  return x > y ? x : y;
}
template <class T>
inline T Min(const T x, const T y) {
  return x < y ? x : y;
}
template <class T>
inline T fab(const T x) {
  return x > 0 ? x : -x;
}
inline int gcd(const int a, const int b) { return b ? gcd(b, a % b) : a; }
inline void getInv(int inv[], const int lim, const int MOD) {
  inv[0] = inv[1] = 1;
  for (int i = 2; i <= lim; ++i)
    inv[i] = 1ll * inv[MOD % i] * (MOD - MOD / i) % MOD;
}
inline long long mulMod(const long long a, const long long b,
                        const long long mod) {
  return ((a * b - (long long)((long double)a / mod * b + 1e-8) * mod) % mod +
          mod) %
         mod;
}
const int MAXN = 2500;
int n, a[MAXN + 5][MAXN + 5];
pair<int, int> t[MAXN * MAXN + 5];
inline void Init() {
  n = read(1);
  for (signed i = (1), i_end_ = (n); i <= i_end_; ++i)
    for (signed j = (1), j_end_ = (n); j <= j_end_; ++j) a[i][j] = read(1);
}
inline bool cmp(const pair<int, int> i, const pair<int, int> j) {
  return a[i.first][i.second] < a[j.first][j.second];
}
vector<pair<int, int> > pos[MAXN * MAXN + 5];
int hcnt;
inline void hasMatrix() {
  for (signed i = (1), i_end_ = (n); i <= i_end_; ++i)
    for (signed j = (1), j_end_ = (n); j <= j_end_; ++j)
      t[(i - 1) * n + j] = make_pair(i, j);
  sort(t + 1, t + (n * n) + 1, cmp);
  int pre = a[t[1].first][t[1].second], hasnum = 1;
  a[t[1].first][t[1].second] = 1;
  for (signed i = (2), i_end_ = (n * n); i <= i_end_; ++i) {
    hasnum += (a[t[i].first][t[i].second] != pre);
    pos[hasnum].push_back(t[i]);
    pre = a[t[i].first][t[i].second];
    a[t[i].first][t[i].second] = hasnum;
  }
  hcnt = hasnum;
}
bitset<MAXN + 5> x[MAXN + 5], y[MAXN + 5], res;
inline void check() {
  int sz, p, q;
  for (signed i = (1), i_end_ = (hcnt); i <= i_end_; ++i) {
    sz = pos[i].size();
    for (signed j = (0), j_end_ = (sz - 1); j <= j_end_; ++j) {
      p = pos[i][j].first, q = pos[i][j].second;
      res = x[p] & y[q];
      if (res.any()) {
        puts("NOT MAGIC");
        return;
      }
    }
    for (signed j = (0), j_end_ = (sz - 1); j <= j_end_; ++j) {
      p = pos[i][j].first, q = pos[i][j].second;
      x[p][q] = y[q][p] = 1;
    }
  }
  puts("MAGIC");
}
signed main() {
  Init();
  for (signed i = (1), i_end_ = (n); i <= i_end_; ++i)
    for (signed j = (1), j_end_ = (n); j <= j_end_; ++j) {
      if (a[i][j] != a[j][i] || (i == j && a[i][j] != 0)) {
        puts("NOT MAGIC");
        return 0;
      }
    }
  hasMatrix();
  check();
  return 0;
}

```