마방진

$n \times n$ 크기의 표에 서로 다른 양의 정수 $n^2$개가 채워져 있고, 모든 행, 모든 열, 그리고 두 대각선의 수의 합이 모두 같을 때, 이 표를 마방진이라고 부른다. 예를 들어 아래 표는 각 행, 각 열, 두 대각선의 합이 모두 $15$인 마방진이다.

2 7 6
9 5 1
4 3 8

오래된 마방진 가운데 일부는 훼손되어, 정확히 $n$개의 칸에 적힌 수가 지워져 있다. 지워진 칸들은 어느 두 칸도 같은 행이나 같은 열에 있지 않다. 즉 모든 행과 모든 열에서 정확히 한 칸씩 지워져 있다. 이렇게 훼손된 표가 주어질 때, 지워진 칸을 다시 채워 표가 마방진이 되도록 복원하여라.

첫째 줄에 마방진의 크기 $n$ ($2 \le n \le 1000$)이 주어진다. 이어지는 $n$개의 줄에는 각각 $n$개의 정수 $a_{ij}$ ($0 \le a_{ij} \le 10^9$)가 공백 하나로 구분되어 주어지며, $i$번째 줄은 표의 $i$번째 행을 나타낸다. 양수 $a_{ij}$는 그 칸에 적힌 값이고, $0$은 값이 지워진 칸을 나타낸다. 지워진 칸은 모두 $n$개이며, 각 행과 각 열에 정확히 하나씩 있다.

복원한 마방진을 $n$개의 줄에 출력한다. 각 줄에는 $n$개의 양의 정수를 공백 하나로 구분하여 출력하며, 각 수는 $10^{18}$ 이하이다. 입력은 항상 마방진으로 복원할 수 있고, 그 복원 결과가 유일하게 정해지도록 주어진다. 따라서 올바른 표는 정확히 하나 존재한다.