Дан набор натуральных чисел: a
1, …, a
N. По этому набору строится таблица чисел размером N x N по следующему правилу: в клетку i-го столбца j-й строки записывается большее из чисел a
i и a
j при i ≠ j (если a
i = a
j, то записывается это число); на пересечении i-го столбца и i-й строки записывается число 0.
Дана таблица чисел. Требуется определить, могла ли она быть построена по данным правилам из какого-либо набора чисел a
1, …, a
N.
Входные данные
В первой строке входных данных задается натуральное число N – размер таблицы (1 ≤ N ≤ 500). В следующих N строках содержится по N чисел – числа соответствующей строки из таблицы (все числа целые неотрицательные и не превосходят 1 000).
Выходные данные
В одну строку выведите через пробел числа a
1, …, a
N. Если решений несколько, выведите любое из них. Если набора, удовлетворяющего данной таблице, не существует, выведите одно число "-1".
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
0 4 6
4 0 6
6 6 0
|
4 4 6
|
|
2
|
2
0 1
2 0
|
-1
|