Bessie ma tablicę dodawania $N\times N$ ($1\le N\le 1000$), gdzie wpis w wierszu $r$ i kolumnie $c$ to $r+c$ dla każdego $1\le r,c\le N$. Na przykład dla $N=3$ wygląda tak:

2 3 4
3 4 5
4 5 6

Niestety Elsie przejęła tablicę i przestawiła ją, wykonując dowolnie wiele operacji trzech typów.

1. Zamienić dwa wiersze

2. Zamienić dwie kolumny

3. Wybrać obecne w tablicy wartości $a$ i $b$ oraz jednocześnie zamienić wszystkie $a$ na $b$ i wszystkie $b$ na $a$.

Typy są zawsze wykonywane rosnąco: dowolnie wiele (być może zero) typu $1$, potem typu $2$, na końcu typu $3$.

Odtwórz możliwy stan po wszystkich operacjach typów $1$ i $2$, lecz przed jakąkolwiek typu $3$. Jeśli odpowiedzi jest wiele, wypisz najmniejszą leksykograficznie.

Aby porównać tablice leksykograficznie, czytaj je w naturalnym porządku (wiersze od góry do dołu, w każdym od lewej do prawej) i porównaj pierwsze różne wpisy.

Wejście

Pierwszy wiersz zawiera $N$.

Kolejne $N$ wierszy zawiera po $N$ liczb całkowitych, tablicę po przestawieniach Elsie.

Wyjście

Wypisz najmniejszy leksykograficznie możliwy stan po wszystkich operacjach typów 1 i 2, ale przed typem 3. Odpowiedź istnieje.

Przykład

Wejście 1

1
2

Wyjście 1

2

Uwagi

Niezależnie od operacji Elsie tablica się nie zmieni.

Wejście 2

3
3 4 2
5 2 3
6 3 5

Wyjście 2

4 2 3
5 3 4
6 4 5

Uwagi

Oto możliwa sekwencja jej operacji.

2 3 4
3 4 5
4 5 6
-> (operacja 1: zamienić kolumny 2 i 3)
2 4 3
3 5 4
4 6 5
-> (operacja 1: zamienić kolumny 1 i 2)
4 2 3
5 3 4
6 4 5
-> (operacja 3: zamienić wartości 2 i 3)
4 3 2
5 2 4
6 4 5
-> (operacja 3: zamienić wartości 3 i 4)
3 4 2
5 2 3
6 3 5

Uwaga: poniższy stan także jest możliwy po typach 1 i 2, lecz nie najmniejszy leksykograficznie, bo drugi wpis pierwszego wiersza jest większy niż w poprawnej odpowiedzi.

4 6 5
3 5 4
2 4 3

Wejście 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

Wyjście 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

Podzadania

• Wejścia 4-5: $N\le 6$
• Wejścia 6-7: $N\le 8$
• Wejścia 8-11: $N\le 100$
• Wejścia 12-15: brak dodatkowych ograniczeń.

Autor zadania: Benjamin Qi