Судоку обычно состоит из $n$ блоков размером $\sqrt{n} \times \sqrt{n}$.

Каждая строка и каждый столбец должны содержать числа от $1$ до $n$ без пропусков и повторений. Каждый блок (область, выделенная жирными линиями, обычно размером $\sqrt{n} \times \sqrt{n}$) также должен содержать числа от $1$ до $n$ без пропусков и повторений. Заполненное судоку должно одновременно удовлетворять всем трем условиям.

На рисунке представлен пример судоку размера $n=9$.

Дан неполный вариант судоку. Требуется добавить любое количество чисел так, чтобы итоговое судоку имело ровно два решения. Среди всех таких способов заполнения необходимо выбрать тот, при котором разница между двумя решениями максимальна. Разница определяется как количество ячеек, в которых значения в двух решениях различаются.

При этом для любых двух позиций в судоку, если $x_1, x_2$ — значения в первой позиции в двух решениях, а $y_1, y_2$ — значения во второй позиции, то не должно одновременно выполняться $x_1\not=x_2, y_1\not=y_2, x_1\not=y_2, x_1 \not = y_1$.

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

Первая строка содержит число $n$ — размер судоку.

Далее следуют $n$ строк, в каждой из которых по $n$ чисел $a_{i,j}$, представляющих неполное судоку. Число $0$ означает пустую ячейку.

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

Выведите $n$ строк по $n$ чисел — заполненное поле. Если существует несколько способов заполнения, обеспечивающих максимальную разницу между двумя решениями, выведите любой из них.

Примеры

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

4
3 0 0 0
0 0 0 0
0 3 0 0
0 0 0 3

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

3 0 0 0
0 0 0 2
0 3 0 0
2 0 0 3

Примечание

Два решения для примера выше:

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

и

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

Сравнив их, можно увидеть, что разница составляет $8$. Можно доказать, что это один из способов достичь максимальной разницы $8$ для данного условия.

Подзадачи

Для подзадачи 1 ограничение по времени составляет 2 с. Для остальных — 30 с.

Для всех тестов: $a_{i,j} \in [0, n]$, гарантируется, что существует хотя бы один способ заполнения, приводящий к ровно двум решениям.