Un Sudoku generalmente consiste en $n$ bloques de $\sqrt{n} \times \sqrt{n}$ en una cuadrícula de $n \times n$.

Cada fila y cada columna deben contener los números del $1$ al $n$, sin faltar ninguno y sin repeticiones. Cada bloque (la región delimitada por líneas gruesas, usualmente de $\sqrt{n} \times \sqrt{n}$) también debe contener los números del $1$ al $n$, sin faltar ninguno y sin repeticiones. Para completar el Sudoku, se deben satisfacer estas tres condiciones simultáneamente.

La figura muestra un ejemplo de un Sudoku de $n=9$.

Dado un Sudoku incompleto, se requiere añadir cualquier cantidad de números de tal manera que el Sudoku completado tenga exactamente dos soluciones, es decir, que posea una solución dual; y se requiere que, entre todas las formas de completar el tablero, la diferencia entre las dos soluciones sea la máxima posible. Aquí, la diferencia se define como la cantidad de celdas en las que los números difieren al comparar ambas soluciones.

Al mismo tiempo, para cualesquiera dos posiciones en el Sudoku, si $x_1, x_2$ representan los números en la primera posición para las dos soluciones, y $y_1, y_2$ representan los números en la segunda posición para las dos soluciones, no se debe cumplir simultáneamente que $x_1 \neq x_2, y_1 \neq y_2, x_1 \neq y_2, x_1 \neq y_1$.

Entrada

La primera línea contiene un número $n$ que representa el tamaño del Sudoku.

Las siguientes $n$ líneas contienen $n$ números ${a_i}_j$ cada una, representando el tablero incompleto. Las posiciones con el número $0$ indican que no hay ningún número asignado.

Salida

$n$ líneas, cada una con $n$ números, mostrando el tablero completado. Si existen múltiples formas de completarlo que satisfacen la condición de máxima diferencia entre sus dos soluciones, puede imprimir cualquiera de ellas.

Ejemplos

Entrada 1

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

Salida 1

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

Nota

Las dos soluciones correspondientes a la salida del ejemplo son:

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

y:

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

Al comparar celda por celda, se obtiene una diferencia de $8$. Se puede demostrar que este es uno de los métodos para alcanzar la diferencia máxima de $8$ para este tablero.

Subtareas

Para todos los datos: $a_{i,j} \in [0,n]$, se garantiza que el Sudoku incompleto dado tiene al menos una forma de completarse que resulta en una solución dual. El tiempo límite para la subtarea 1 es de 2s, y para el resto es de 30s.