Bessie ha una tabella di addizione $N\times N$ ($1\le N\le 1000$), la cui voce alla riga $r$ e colonna $c$ vale $r+c$ per ogni $1\le r,c\le N$. Per esempio, per $N=3$ sarebbe:

2 3 4
3 4 5
4 5 6

Purtroppo Elsie ha preso la tabella e l'ha permutata eseguendo i seguenti tre tipi di operazioni quante volte voleva.

1. Scambiare due righe

2. Scambiare due colonne

3. Scegliere due valori $a$ e $b$ presenti e sostituire simultaneamente tutti gli $a$ con $b$ e tutti i $b$ con $a$.

I tipi sono sempre eseguiti in ordine crescente: quante operazioni desidera (anche nessuna) di tipo $1$, poi tipo $2$, infine tipo $3$.

Ricostruisci uno stato possibile dopo tutte le operazioni di tipi $1$ e $2$, ma prima di qualsiasi operazione di tipo $3$. Se ci sono più risposte, stampa la minima lessicograficamente.

Per confrontare tabelle lessicograficamente, leggile nell'ordine naturale (righe dall'alto al basso, da sinistra a destra in ogni riga) e confronta le prime voci diverse.

Input

La prima riga contiene $N$.

Le successive $N$ righe contengono $N$ interi ciascuna, la tabella dopo le permutazioni di Elsie.

Output

Stampa il minimo stato possibile lessicograficamente dopo tutte le operazioni dei tipi 1 e 2, ma prima di quelle del tipo 3. La risposta esiste sicuramente.

Esempi

Input 1

1
2

Output 1

2

Nota

Qualunque operazione faccia Elsie, la tabella non cambia.

Input 2

3
3 4 2
5 2 3
6 3 5

Output 2

4 2 3
5 3 4
6 4 5

Nota

Questa è una possibile sequenza delle sue operazioni.

2 3 4
3 4 5
4 5 6
-> (op 1: scambiare colonne 2 e 3)
2 4 3
3 5 4
4 6 5
-> (op 1: scambiare colonne 1 e 2)
4 2 3
5 3 4
6 4 5
-> (op 3: scambiare valori 2 e 3)
4 3 2
5 2 4
6 4 5
-> (op 3: scambiare valori 3 e 4)
3 4 2
5 2 3
6 3 5

Nota: lo stato seguente è possibile dopo i tipi 1 e 2, ma non è il minimo lessicografico, perché la seconda voce della prima riga è maggiore che nella risposta corretta.

4 6 5
3 5 4
2 4 3

Input 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

Output 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

Sottoproblemi

• Input 4-5: $N\le 6$
• Input 6-7: $N\le 8$
• Input 8-11: $N\le 100$
• Input 12-15: nessun vincolo aggiuntivo.

Autore del problema: Benjamin Qi