Bessie tiene una tabla de suma $N\times N$ ($1\le N\le 1000$), donde la entrada de fila $r$ y columna $c$ es $r+c$ para todo $1\le r,c\le N$. Por ejemplo, para $N=3$ sería:

2 3 4
3 4 5
4 5 6

Por desgracia, Elsie tomó la tabla y la permutó realizando las siguientes tres clases de operaciones tantas veces como quiso.

1. Intercambiar dos filas

2. Intercambiar dos columnas

3. Elegir dos valores $a$ y $b$ presentes en la tabla y cambiar simultáneamente todos los $a$ por $b$ y todos los $b$ por $a$.

Los tipos se realizan siempre en orden creciente: tantas operaciones como quiera (posiblemente ninguna) de tipo $1$, después de tipo $2$, y al final de tipo $3$.

Recupera un posible estado tras todas las operaciones de tipos $1$ y $2$, pero antes de cualquiera de tipo $3$. Si hay varias respuestas, imprime la menor lexicográficamente.

Para comparar tablas lexicográficamente, léelas en orden natural (filas de arriba abajo, cada fila de izquierda a derecha) y compara las primeras entradas distintas.

Entrada

La primera línea contiene $N$.

Las siguientes $N$ líneas contienen $N$ enteros cada una, la tabla de suma después de las permutaciones de Elsie.

Salida

Imprime el menor estado posible lexicográficamente tras todas las operaciones de tipos 1 y 2, pero antes de cualquiera de tipo 3. Se garantiza que existe respuesta.

Ejemplos

Entrada 1

1
2

Salida 1

2

Nota

Sin importar qué operaciones haga Elsie, la tabla no cambia.

Entrada 2

3
3 4 2
5 2 3
6 3 5

Salida 2

4 2 3
5 3 4
6 4 5

Nota

Esta es una posible secuencia de operaciones de Elsie.

2 3 4
3 4 5
4 5 6
-> (op 1: intercambiar columnas 2 y 3)
2 4 3
3 5 4
4 6 5
-> (op 1: intercambiar columnas 1 y 2)
4 2 3
5 3 4
6 4 5
-> (op 3: intercambiar valores 2 y 3)
4 3 2
5 2 4
6 4 5
-> (op 3: intercambiar valores 3 y 4)
3 4 2
5 2 3
6 3 5

Nota: el siguiente estado también es posible tras los tipos 1 y 2, pero no es el menor lexicográficamente porque la segunda entrada de la primera fila es mayor que en la respuesta correcta.

4 6 5
3 5 4
2 4 3

Entrada 3

6
8 10 5 6 7 4
12 11 10 4 8 2
5 4 6 7 9 8
10 2 4 8 5 12
6 8 7 9 3 5
4 12 8 5 6 10

Salida 3

7 5 8 9 10 6
4 2 5 6 7 3
8 6 9 10 11 7
5 3 6 7 8 4
9 7 10 11 12 8
6 4 7 8 9 5

Subtareas

• Entradas 4-5: $N\le 6$
• Entradas 6-7: $N\le 8$
• Entradas 8-11: $N\le 100$
• Entradas 12-15: sin restricciones adicionales.

Autor del problema: Benjamin Qi