У Bessie есть таблица сложения $N\times N$ ($1\le N\le 1000$), где в строке $r$ и столбце $c$ стоит $r+c$ для всех $1\le r,c\le N$. Например, при $N=3$ она выглядит так:

2 3 4
3 4 5
4 5 6

К сожалению, Elsie получила таблицу и переставила её, выполняя сколько угодно операций трёх типов.

1. Поменять две строки

2. Поменять два столбца

3. Выбрать присутствующие в таблице значения $a$ и $b$ и одновременно заменить все $a$ на $b$, а все $b$ на $a$.

Elsie всегда выполняет операции по возрастанию типа: сначала сколько угодно (возможно, ни одной) типа $1$, затем типа $2$, наконец типа $3$.

Восстановите возможную таблицу после всех операций типов $1$ и $2$, но до любой операции типа $3$. Если ответов несколько, выведите лексикографически минимальный.

Для лексикографического сравнения читайте таблицы в естественном порядке (строки сверху вниз, внутри строки слева направо) и сравните первые различающиеся элементы.

Входные данные

Первая строка содержит $N$.

Следующие $N$ строк содержат по $N$ целых чисел — таблицу после перестановок Elsie.

Выходные данные

Выведите лексикографически минимальную возможную таблицу после всех операций типов 1 и 2, но до типа 3. Ответ гарантированно существует.

Примеры

Входные данные 1

1
2

Выходные данные 1

2

Примечание

Какие бы операции ни выполняла Elsie, таблица не изменится.

Входные данные 2

3
3 4 2
5 2 3
6 3 5

Выходные данные 2

4 2 3
5 3 4
6 4 5

Примечание

Вот возможная последовательность её операций.

2 3 4
3 4 5
4 5 6
-> (операция 1: поменять столбцы 2 и 3)
2 4 3
3 5 4
4 6 5
-> (операция 1: поменять столбцы 1 и 2)
4 2 3
5 3 4
6 4 5
-> (операция 3: поменять значения 2 и 3)
4 3 2
5 2 4
6 4 5
-> (операция 3: поменять значения 3 и 4)
3 4 2
5 2 3
6 3 5

Примечание: следующая таблица также возможна после типов 1 и 2, но не лексикографически минимальна: второй элемент первой строки больше, чем в правильном ответе.

4 6 5
3 5 4
2 4 3

Входные данные 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

Выходные данные 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

Подзадачи

• Входы 4-5: $N\le 6$
• Входы 6-7: $N\le 8$
• Входы 8-11: $N\le 100$
• Входы 12-15: дополнительных ограничений нет.

Автор задачи: Benjamin Qi