Sudoku składa się zazwyczaj z $n$ bloków o rozmiarze $\sqrt{n} \times \sqrt{n}$.

Każdy wiersz i każda kolumna muszą zawierać liczby od $1$ do $n$, bez braków i powtórzeń. Każdy blok (obszar otoczony grubą linią, zazwyczaj o rozmiarze $\sqrt{n} \times \sqrt{n}$) również musi zawierać liczby od $1$ do $n$, bez braków i powtórzeń. Rozwiązanie musi spełniać wszystkie trzy warunki jednocześnie.

Rysunek przedstawia przykład Sudoku o rozmiarze $n=9$.

Dany jest niekompletny diagram Sudoku. Należy uzupełnić dowolną liczbę komórek tak, aby po uzupełnieniu Sudoku miało dokładnie dwa rozwiązania (tzw. rozwiązanie podwójne). Spośród wszystkich takich uzupełnień należy wybrać to, dla którego różnica między tymi dwoma rozwiązaniami jest największa. Różnica jest zdefiniowana jako liczba komórek, w których wartości w obu rozwiązaniach są różne.

Dodatkowo, dla dowolnych dwóch pozycji w Sudoku, jeśli $x_1, x_2$ oznaczają wartości w tych pozycjach w pierwszym rozwiązaniu, a $y_1, y_2$ oznaczają wartości w tych samych pozycjach w drugim rozwiązaniu, to nie mogą jednocześnie zachodzić warunki $x_1\neq x_2, y_1\neq y_2, x_1\neq y_2, x_1\neq y_1$.

Wejście

W pierwszej linii znajduje się liczba $n$ określająca rozmiar Sudoku.

W kolejnych $n$ liniach znajduje się po $n$ liczb ${a_i}_j$, reprezentujących niekompletny diagram Sudoku. Wartość $0$ oznacza puste pole.

Wyjście

Wypisz $n$ linii, każda zawierająca $n$ liczb, reprezentujących uzupełnioną planszę. Jeśli istnieje wiele sposobów uzupełnienia spełniających warunek maksymalnej różnicy, można wypisać dowolny z nich.

Przykład

Wejście 1

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

Wyjście 1

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

Uwagi

Dla powyższego wyjścia dwa rozwiązania to:

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

oraz:

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

Porównując komórka po komórce, otrzymujemy różnicę wynoszącą $8$. Można udowodnić, że jest to jedna z metod osiągających maksymalną możliwą różnicę dla tego zadania.

Ograniczenia

Dla podzadania 1 limit czasu wynosi 2s. Dla pozostałych limit czasu wynosi 30s.

Dla wszystkich danych: $a_{i,j} \in [0,n]$, gwarantuje się, że dla podanego niekompletnego diagramu istnieje przynajmniej jeden sposób uzupełnienia prowadzący do dokładnie dwóch rozwiązań.