CF274D.Lovely Matrix

Lenny had an n × m matrix of positive integers. He loved the matrix so much, because each row of the matrix was sorted in non-decreasing order. For the same reason he calls such matrices of integers lovely.

One day when Lenny was at school his little brother was playing with Lenny's matrix in his room. He erased some of the entries of the matrix and changed the order of some of its columns. When Lenny got back home he was very upset. Now Lenny wants to recover his matrix.

Help him to find an order for the columns of the matrix so that it's possible to fill in the erased entries of the matrix to achieve a lovely matrix again. Note, that you can fill the erased entries of the matrix with any integers.

Lenny 有一个 $n \times m$ 的正整数矩阵。他非常喜爱这个矩阵，因为该矩阵的每一行都是按非递减顺序排列的。出于同样的原因，他将这类整数矩阵称为“可爱的”（lovely）。

有一天，Lenny 在学校上课时，他的弟弟在他的房间里玩 Lenny 的矩阵。他擦除了矩阵中的一些元素，并且打乱了某些列的顺序。当 Lenny 回到家时，他非常沮丧。现在 Lenny 想要恢复他的矩阵。

请你帮他找出一种列的排列顺序，使得我们能够用任意整数填充被擦除的矩阵元素，从而再次得到一个“可爱的”矩阵。注意：你可以用任意整数来填充被擦除的矩阵元素。

The first line of the input contains two positive integers n and m (1 ≤ n·m ≤ 105). Each of the next n lines contains m space-separated integers representing the matrix. An integer -1 shows an erased entry of the matrix. All other integers (each of them is between 0 and 109 inclusive) represent filled entries.

输入的第一行包含两个正整数 $n$ 和 $m$（满足 $1 \leq n\cdot m \leq 10^5$）。接下来的 $n$ 行中，每行包含 $m$ 个以空格分隔的整数，表示该矩阵。整数 $-1$ 表示矩阵中被擦除的条目；其余所有整数（均在 $0$ 到 $10^9$ 之间，含端点）表示已填入的条目。

If there exists no possible reordering of the columns print -1. Otherwise the output should contain m integers _p_1, _p_2, ..., p__m showing the sought permutation of columns. So, the first column of the lovely matrix will be _p_1-th column of the initial matrix, the second column of the lovely matrix will be _p_2-th column of the initial matrix and so on.

如果不存在可能的列重排方案，则输出 -1。否则，输出应包含 m 个整数 _p_₁, _p_₂, ..., p__m，表示所求的列排列。即：优美矩阵的第一列是原矩阵的第 _p_₁ 列，优美矩阵的第二列是原矩阵的第 _p_₂ 列，依此类推。