Magic Square Validator

Given an odd-sized square matrix, determine whether it forms a valid magic square.

A magic square is a square arrangement of numbers where the sum of the numbers in each row, each column, and both main diagonals is equal. This common sum is known as the magic constant. Additionally, the square must contain all integers from \(1\) to \(n^2\) exactly once.

If the matrix is a valid magic square, output the magic constant. Otherwise, output NOT MAGIC.

inputFormat

The input is given via standard input (stdin) and consists of two lines:

1. The first line contains a single odd positive integer \(n\), representing the size of the matrix.
2. The second line contains \(n^2\) space-separated integers describing the matrix in row-major order.

outputFormat

Output a single line to standard output (stdout) containing the magic constant if the matrix is a valid magic square, or NOT MAGIC otherwise.

3
8 1 6 3 5 7 4 9 2

15