У Боба есть перестановка целых чисел от 1 до n. Обозначим эту перестановку как p, при этом i-й элемент p обозначается как pi. Для всех пар различных индексов i, j (1 ≤ i, j ≤ n) Боб выписал число ai, j = min(pi, pj). При этом ai, i = 0 для всех целых i от 1 до n.
Боб дал вам все выписанные им значения ai, j. Ваша задача — восстановить какую-нибудь перестановку размера n, по которой могли быть получены такие значения, если известно, что хотя бы одна такая перестановка существует.
Выходные данные
Выведите перестановку из n целых чисел, по которой могли бы быть получены такие значения ai, j. Если существует несколько возможных решений, то разрешается вывести любое из них.
Примечание
В первом примере подходят перестановки {1, 2} или {2, 1}.
Во втором примере ещё одной подходящей перестановкой является {2, 4, 5, 1, 3}.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
0 1
1 0
|
2 1
|
|
2
|
5
0 2 2 1 2
2 0 4 1 3
2 4 0 1 3
1 1 1 0 1
2 3 3 1 0
|
2 5 4 1 3
|