Bessie a une table d'addition $N\times N$ ($1\le N\le 1000$) dont l'entrée de ligne $r$ et colonne $c$ vaut $r+c$ pour tout $1\le r,c\le N$. Par exemple, pour $N=3$, elle serait :

2 3 4
3 4 5
4 5 6

Malheureusement, Elsie s'en est emparée et l'a permutée en effectuant autant d'opérations des trois types suivants qu'elle voulait.

1. Échanger deux lignes

2. Échanger deux colonnes

3. Choisir deux valeurs $a$ et $b$ présentes dans la table, puis remplacer simultanément tous les $a$ par $b$ et tous les $b$ par $a$.

Les types sont toujours appliqués dans l'ordre croissant : autant d'opérations que voulu (éventuellement aucune) de type $1$, puis de type $2$, enfin de type $3$.

Retrouvez une table possible après toutes les opérations de types $1$ et $2$, mais avant toute opération de type $3$. Si plusieurs réponses existent, affichez la plus petite lexicographiquement.

Pour comparer deux tables lexicographiquement, lisez-les dans l'ordre naturel (lignes de haut en bas, de gauche à droite dans chaque ligne) et comparez leurs premières entrées différentes.

Entrée

La première ligne contient $N$.

Les $N$ lignes suivantes contiennent chacune $N$ entiers : la table d'addition après les permutations d'Elsie.

Sortie

Affichez l'état possible minimal lexicographiquement après toutes les opérations de types 1 et 2, mais avant celles de type 3. L'existence d'une réponse est garantie.

Exemples

Entrée 1

1
2

Sortie 1

2

Remarque

Quelles que soient les opérations, la table ne change pas.

Entrée 2

3
3 4 2
5 2 3
6 3 5

Sortie 2

4 2 3
5 3 4
6 4 5

Remarque

Voici une séquence d'opérations qu'Elsie aurait pu effectuer.

2 3 4
3 4 5
4 5 6
-> (op 1 : échanger les colonnes 2 et 3)
2 4 3
3 5 4
4 6 5
-> (op 1 : échanger les colonnes 1 et 2)
4 2 3
5 3 4
6 4 5
-> (op 3 : échanger les valeurs 2 et 3)
4 3 2
5 2 4
6 4 5
-> (op 3 : échanger les valeurs 3 et 4)
3 4 2
5 2 3
6 3 5

Remarque : l'état suivant est aussi possible après les types 1 et 2, mais n'est pas le plus petit lexicographiquement, car la deuxième entrée de la première ligne est plus grande que dans la bonne réponse.

4 6 5
3 5 4
2 4 3

Entrée 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

Sortie 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

Sous-tâches

• Entrées 4-5 : $N\le 6$
• Entrées 6-7 : $N\le 8$
• Entrées 8-11 : $N\le 100$
• Entrées 12-15 : aucune contrainte supplémentaire.

Auteur du problème : Benjamin Qi