Перед Беси находится \(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
Эльза поменяла числа в таблице, выполняя произвольное количество раз
операции следующих трёх типов:
- Поменять две строки
- Поменять два столбца
- Выбрать два значения \(a\) и \(b\) из присутствующих в таблице,
а затем одновременно поменять все вхождения \(a\) на \(b\) и все возможные
вхождения \(b\) на \(a\).
Эльза всегда выполняет операции в порядке возрастания типа:
сначала все операции (возможно ни одной) типа \(1\),
затем типа \(2\), затем типа \(3\).
Помогите Беси восстановить возможное состояние таблицы после того как Эльза
выполнит все операции типов \(1\) и \(2\), но прежде чем она выполнит первую операцию
типа \(3\). Если возможно много вариантов ответов выберите лексикографически минимальный.
Чтобы сравнивать таблицы лексикографически сравните первые величины где они отличаются.
Рассматривая обе таблицы в естественном порядке (строки сверху вниз,
в строке слева направо).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\).
Каждая из следующих \(N\) строк содержит \(N\) целых чисел, представляющих таблицу сложения
Беси после того, как Эльза перепутала её.
ФОРМАТ ВЫВОДА (на экран / stdout):
Лексикографически минимальное состояние таблицы после всех операций типа \(1\) и \(2\),
но перед выполнением первой операции типа \(3\). Гарантируется, что ответ существует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
2
|
2
|