Un Sudoku est généralement composé de $n$ blocs de taille $\sqrt{n} \times \sqrt{n}$.

Chaque ligne et chaque colonne doit contenir les nombres de $1$ à $n$, sans omission ni répétition. Chaque bloc (la zone délimitée par des lignes épaisses, généralement de taille $\sqrt{n} \times \sqrt{n}$) doit également contenir les nombres de $1$ à $n$, sans omission ni répétition. Une grille complétée doit satisfaire simultanément ces trois conditions.

La figure ci-dessus montre un exemple de Sudoku de taille $n=9$.

Étant donné une grille de Sudoku incomplète, vous devez ajouter un nombre quelconque de chiffres de telle sorte que la grille complétée possède exactement deux solutions. De plus, parmi toutes les méthodes de complétion possibles, vous devez choisir celle pour laquelle la différence entre les deux solutions est maximale. Ici, la différence est définie comme le nombre de cellules où les deux solutions diffèrent.

Par ailleurs, pour deux positions quelconques dans le Sudoku, si $x_1, x_2$ représentent les valeurs des deux solutions à la première position, et $y_1, y_2$ les valeurs à la seconde position, alors il ne doit pas être vrai que $x_1 \neq x_2$, $y_1 \neq y_2$, $x_1 \neq y_2$ et $x_1 \neq y_1$ soient tous satisfaits simultanément.

Entrée

La première ligne contient un entier $n$ représentant la taille du Sudoku.

Les $n$ lignes suivantes contiennent chacune $n$ entiers $a_{i,j}$, représentant la grille incomplète. Les positions contenant $0$ indiquent des cases vides.

Sortie

Affichez $n$ lignes, chacune contenant $n$ entiers, représentant la grille complétée. S'il existe plusieurs façons de compléter la grille pour obtenir une différence maximale entre les deux solutions, n'importe laquelle d'entre elles est acceptée.

Exemples

Entrée 1

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

Sortie 1

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

Remarque

Les deux solutions correspondant à la sortie de l'exemple sont :

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

et :

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

En comparant cellule par cellule, on obtient une différence de $8$. On peut prouver qu'il s'agit de l'une des méthodes permettant d'atteindre la valeur maximale de $8$ pour cette grille.

Contraintes

Pour toutes les données : $a_{i,j} \in [0, n]$, et il est garanti qu'il existe au moins une façon de compléter la grille initiale pour qu'elle possède exactement deux solutions.