Quadrado Mágico

Arnaldo e Bernardo são dois garotos que compartilham um peculiar gosto por curiosidades matemáticas. Nos últimos tempos, sua principal diversão tem sido investigar propriedades matemágicas de tabuleiros quadrados preenchidos com inteiros. Recentemente, durante uma aula de matemática, os dois desaaram os outros alunos da classe a criar quadrados mágicos, que são quadrados preenchidos com números de 1 a N², de tal forma que a soma dos N números em uma linha, coluna ou diagonal principal do quadrado tenham sempre o mesmo valor. A ordem de um quadrado mágico é o seu número de linhas, e o valor do quadrado mágico é o resultado da soma de uma linha. Um exemplo de quadrado mágico de ordem 3 e valor 15 é mostrado na figura abaixo:

Entrada

A primeira linha da entrada contém um único número inteiro N, indicando a ordem do quadrado (seu número de linhas). As N linhas seguintes descrevem o quadrado. Cada uma dessas linhas contém N números inteiros separados por um espaço em branco.

Saída

Seu programa deve imprimir uma única linha na saída padrão. Caso o quadrado seja mágico, a linha deve conter o valor do quadrado (ou seja, a soma de uma de suas linhas). Caso contrário, a linha deve conter o número 0.

Restrições

• 3 ≤ N ≤ 1000
• 2 ≤ valor de cada célula ≤ 10⁹

Informações sobre a pontuação

• Em um conjunto de casos de teste que totaliza 30 pontos, N ≤ 3.
• Em um conjunto de casos de teste que totaliza 70 pontos, N ≤ 100.

Exemplos

3
1 1 1
1 1 1
1 1 1

0

4
16 3 2 13
5 10 11 8
9 6 7 12
4 15 14 1

34

3
4 8 9
11 7 3
6 5 10

0