302_restore_the_matrix

302. Восстановить матрицу

Description

Для создания сервиса бонусов была предложена следующая схема:

• Выбирается целое число $n$.
• В помеченные ячейки матрицы $n \times n$ записываются $n$ различных чисел от $1$ до $n^2$.
• Остальные $n^2-n$ ячеек остаются пустыми.
• Пользователь получает бонус, если угадывает числа, расположенные в помеченных ячейках.

Для получения бонуса нужно заполнить матрицу $n \times n$ таким образом, чтобы все числа от $1$ до $n^2$ встречались ровно один раз, а во всех помеченных ячейках числа совпадали с выигрышным шаблоном.

Найдите любую выигрышную матрицу.

Input Format:

В первой строке входных данных записано целое число $n$ ($2 \le n \le 100$).

Далее в $n$ строках записаны числа в матрице-шаблоне $a_{ij}$ ($0 \le a_{ij} \le n^2$).

Если $a_{ij}=0$, то соответствующая ячейка матрицы не является помеченной и должна быть заполнена. Если $a_{ij} \ne 0$, то в соответствующую ячейку матрицы нужно вписать $a_{ij}$.

Output Format:

Выведите $n$ строк по $n$ целых чисел — любую из выигрышных матриц.

Гарантируется, что существует как минимум одна выигрышная матрица.

Example Test Cases

Example 1

Input:

4
0 0 0 0
1 2 3 4
0 0 0 0
0 0 0 0

Output:

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

Example 2

Input:

4
1 0 0 0
0 6 0 0
0 0 11 0
0 0 0 16

Output:

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

Example 3

Input:

3
0 0 0
0 0 0
3 2 1

Output:

9 5 4
6 7 8
3 2 1

Tags: implementation, greedy, data structures, constructive, std