F. Волшебная матрица
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задана матрица A размера n × n.

Будем называть матрицу с неотрицательными элементами волшебной, если она симметрична (то есть aij = aji), aii = 0 и aij ≤ max(aik, ajk) для всех троек i, j, k. Заметим, что i, j, k не обязательно различны.

Определите является ли матрица волшебной.

Рекомендуется для ввода и вывода данных использовать функции scanf, printf в языке C++, поскольку они работают значительно быстрее чем cin, cout. Аналогично, рекомендуется использовать классы BufferedReader, PrintWriter вместо Scanner, System.out в языке Java.

Входные данные

В первой строке находится целое число n (1 ≤ n ≤ 2500) — размер матрицы A.

В каждой из следующих n строк находится n целых чисел aij (0 ≤ aij < 109) — элементы матрицы A.

Заметим, что заданная матрица не обязательно является симметричной и может быть произвольной.

Выходные данные

Выведите ''MAGIC" (без кавычек) если матрица A является магической. В противном случае выведите ''NOT MAGIC".

Примеры
Входные данные
3
0 1 2
1 0 2
2 2 0
Выходные данные
MAGIC
Входные данные
2
0 1
2 3
Выходные данные
NOT MAGIC
Входные данные
4
0 1 2 3
1 0 3 4
2 3 0 5
3 4 5 0
Выходные данные
NOT MAGIC