D. Прекрасная матрица
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Ленни была матрица размера n × m, состоящая из целых чисел. Он обожал эту матрицу, поскольку числа в каждой строке матрицы были отсортированы в порядке неубывания. Матрицы, которые обладают таким свойством, Ленни называет прекрасными.

Однажды, когда Ленни был в школе, его младший брат играл с матрицей Ленни в своей комнате. Он стер некоторые записи в матрице и изменил порядок некоторых ее столбцов. Придя домой, Ленни очень опечалился и теперь хочет восстановить свою матрицу.

Помогите ему найти порядок столбцов матрицы так, чтобы было возможно заполнить стертые записи и снова получить прекрасную матрицу. Обратите внимание, что стертые записи можно заполнять любыми целыми числами.

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

Первая строка входных данных содержит два положительных целых числа n и m (1 ≤ n·m ≤ 105). Каждая из следующих n строк содержит m целых чисел через пробел — матрица Ленни. Число -1 обозначает стертую запись в матрице. Все остальные целые числа (каждое из которых между 0 и 109, включительно) представляют заполненные записи.

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

Если не существует возможных способов переупорядочить столбцы, выведите -1. В противном случае, выходные данные должны содержать m целых чисел p1, p2, ..., pm, обозначающих искомую перестановку столбцов. Таким образом, первый столбец прекрасной матрицы будет p1-ым столбцом изначальной матрицы. Второй столбец прекрасной матрицы будет p2-ым столбцом изначальной матрицы и так далее.

Примеры
Входные данные
3 3
1 -1 -1
1 2 1
2 -1 1
Выходные данные
3 1 2
Входные данные
2 3
1 2 2
2 5 4
Выходные данные
1 3 2
Входные данные
2 3
1 2 3
3 2 1
Выходные данные
-1