Bessie tem uma tabela de adição $N\times N$ ($1\le N\le 1000$), cuja entrada na linha $r$ e coluna $c$ é $r+c$ para todo $1\le r,c\le N$. Por exemplo, para $N=3$ seria:

2 3 4
3 4 5
4 5 6

Infelizmente, Elsie apoderou-se da tabela e permutou-a, executando as seguintes três operações tantas vezes quantas quis.

1. Trocar duas linhas

2. Trocar duas colunas

3. Escolher dois valores $a$ e $b$ presentes na tabela e substituir simultaneamente todos os $a$ por $b$ e todos os $b$ por $a$.

Os tipos são sempre executados por ordem crescente: tantas operações como quiser (possivelmente nenhuma) de tipo $1$, depois de tipo $2$, finalmente de tipo $3$.

Recupere um estado possível após todas as operações dos tipos $1$ e $2$, mas antes de qualquer operação do tipo $3$. Se houver várias respostas, imprima a menor lexicograficamente.

Para comparar tabelas lexicograficamente, leia-as na ordem natural (linhas de cima para baixo, cada linha da esquerda para a direita) e compare as primeiras entradas diferentes.

Entrada

A primeira linha contém $N$.

As $N$ linhas seguintes contêm $N$ inteiros cada, a tabela de adição após as permutações de Elsie.

Saída

Imprima o estado possível mínimo lexicograficamente após todas as operações dos tipos 1 e 2, mas antes de qualquer do tipo 3. A existência da resposta é garantida.

Exemplos

Entrada 1

1
2

Saída 1

2

Nota

Quaisquer que sejam as operações, a tabela não muda.

Entrada 2

3
3 4 2
5 2 3
6 3 5

Saída 2

4 2 3
5 3 4
6 4 5

Nota

Esta é uma sequência de operações que Elsie poderá ter realizado.

2 3 4
3 4 5
4 5 6
-> (op 1: trocar colunas 2 e 3)
2 4 3
3 5 4
4 6 5
-> (op 1: trocar colunas 1 e 2)
4 2 3
5 3 4
6 4 5
-> (op 3: trocar valores 2 e 3)
4 3 2
5 2 4
6 4 5
-> (op 3: trocar valores 3 e 4)
3 4 2
5 2 3
6 3 5

Nota: o estado seguinte também é possível após os tipos 1 e 2, mas não é o menor lexicograficamente, pois a segunda entrada da primeira linha é maior que na resposta correta.

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

Saída 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

Subtarefas

• Entradas 4-5: $N\le 6$
• Entradas 6-7: $N\le 8$
• Entradas 8-11: $N\le 100$
• Entradas 12-15: sem restrições adicionais.

Autor do problema: Benjamin Qi