Matrix Replacement without Conflicts

You are given an \(N \times M\) matrix \(A\) satisfying the following properties:

• \(M > N\).
• Every element of \(A\) is a natural number in \([0,N]\) (i.e. between 0 and \(N\), inclusive).
• In each row, every number from \(1\) to \(N\) appears exactly once and \(0\) appears exactly \(M-N\) times.
• In each column, every number from \(1\) to \(N\) appears at most once.

Now, you must choose in each row one nonzero element. Let the chosen number in row \(i\) be \(v_i\), and assume it appears in column \(x_i\) (the position in that row where \(A[i][x_i]=v_i\)). Then for every row, for every column after the chosen element (i.e. for every column \(c\) where \(c > x_i\)), set \(A[i][c] = v_i\).

The resulting matrix must still satisfy property (4): in every column, every number from \(1\) to \(N\) appears at most once.

It can be proved that in order to avoid duplicating any nonzero number in a column, the \(N\) chosen numbers \(v_1, v_2, \dots, v_N\) must be all distinct (i.e. form a permutation of \(\{1,2,\dots,N\}\)). Moreover, if we fix the row order as given (row 1 to row \(N\)), then for every pair of rows \(i\) and \(j\) with \(i < j\), the following condition must hold in row \(j\): \[ \text{pos}(j, v_j) < \text{pos}(j, v_i), \] where \(\text{pos}(j, k)\) is the (unique) column index in row \(j\) where the number \(k\) appears in the original matrix. In other words, if row \(j\) chooses its nonzero \(v_j\) (which appears at column \(x_j\)), then for every row \(i\) with \(i < j\) (with chosen number \(v_i\)), the unique occurrence of \(v_i\) in row \(j\) must appear strictly to the right of column \(x_j\).

Your task is to decide whether there exists a selection of one nonzero per row (i.e. an assignment of a permutation \(p:[1,N]\to[1,N]\) such that for every row \(j\) (\(2 \le j \le N\)), \(\text{pos}(j, p(j)) < \text{pos}(j, p(i))\) for all \(i < j\)) and, if so, output the chosen column indices \(x_1,x_2,\dots,x_N\) (each 1-indexed). If no valid selection exists, output \(-1\).

Note: The chosen column for row \(i\) is forced by the fact that the row contains every number from \(1\) to \(N\) exactly once.

inputFormat

The first line contains two integers \(N\) and \(M\) (with \(M > N\)). Each of the next \(N\) lines contains \(M\) integers describing a row of the matrix \(A\). It is guaranteed that:

• Every row contains each number from \(1\) to \(N\) exactly once and \(0\) exactly \(M-N\) times.
• In every column, each number from \(1\) to \(N\) appears at most once.

The matrix indices are 1-indexed.

outputFormat

If there is a valid selection, output a single line containing \(N\) integers: the chosen column indices (1-indexed) for rows \(1,2,\dots,N\) respectively. Otherwise, output \(-1\).

sample

2 3
1 0 2
2 1 0

1 1