Bessie hat eine Additionstabelle $N\times N$ ($1\le N\le 1000$), deren Eintrag in Zeile $r$ und Spalte $c$ für alle $1\le r,c\le N$ gleich $r+c$ ist. Für $N=3$ sieht sie zum Beispiel so aus:

2 3 4
3 4 5
4 5 6

Leider hat Elsie die Tabelle genommen und mit beliebig vielen Operationen der folgenden drei Typen umgeordnet.

1. Zwei Zeilen vertauschen

2. Zwei Spalten vertauschen

3. Zwei vorhandene Werte $a$ und $b$ auswählen und gleichzeitig alle $a$ durch $b$ und alle $b$ durch $a$ ersetzen.

Die Typen werden stets aufsteigend ausgeführt: zuerst beliebig viele (auch keine) vom Typ $1$, dann Typ $2$, zuletzt Typ $3$.

Rekonstruiere einen möglichen Zustand nach allen Operationen der Typen $1$ und $2$, aber vor jeder Operation vom Typ $3$. Gibt es mehrere Antworten, gib die lexikografisch kleinste aus.

Zum lexikografischen Vergleich lies die Tabellen in natürlicher Reihenfolge (Zeilen von oben nach unten, innerhalb jeder Zeile von links nach rechts) und vergleiche die ersten unterschiedlichen Einträge.

Eingabe

Die erste Zeile enthält $N$.

Die nächsten $N$ Zeilen enthalten jeweils $N$ ganze Zahlen, die Additionstabelle nach Elsies Umordnungen.

Ausgabe

Gib den lexikografisch kleinsten möglichen Zustand nach allen Operationen der Typen 1 und 2, aber vor Typ 3 aus. Eine Antwort existiert garantiert.

Beispiele

Eingabe 1

1
2

Ausgabe 1

2

Hinweis

Unabhängig von Elsies Operationen ändert sich die Tabelle nicht.

Eingabe 2

3
3 4 2
5 2 3
6 3 5

Ausgabe 2

4 2 3
5 3 4
6 4 5

Hinweis

Hier ist eine mögliche Folge ihrer Operationen.

2 3 4
3 4 5
4 5 6
-> (Op 1: Spalten 2 und 3 vertauschen)
2 4 3
3 5 4
4 6 5
-> (Op 1: Spalten 1 und 2 vertauschen)
4 2 3
5 3 4
6 4 5
-> (Op 3: Werte 2 und 3 vertauschen)
4 3 2
5 2 4
6 4 5
-> (Op 3: Werte 3 und 4 vertauschen)
3 4 2
5 2 3
6 3 5

Hinweis: Der folgende Zustand ist ebenfalls nach Typ 1 und 2 möglich, aber nicht lexikografisch minimal, weil der zweite Eintrag der ersten Zeile größer als in der richtigen Antwort ist.

4 6 5
3 5 4
2 4 3

Eingabe 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

Ausgabe 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

Teilaufgaben

• Eingaben 4-5: $N\le 6$
• Eingaben 6-7: $N\le 8$
• Eingaben 8-11: $N\le 100$
• Eingaben 12-15: keine weiteren Einschränkungen.

Autor der Aufgabe: Benjamin Qi