问题 B: 表格

问题 B: 表格

时间限制: 1 Sec  内存限制: 256 MB  Special Judge
提交: 4  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

给出一个表格,N行M列,每个格子有一个整数,有些格子是空的。现在需要你来做出一些调整,使得每行都是非降序的。这个调整只能是整列的移动。

输入

第一行两个正整数 N 和 M。

接下来 N 行,每行 M 个整数,-1 表示这个格子是空的,其他的整数都在 [0, 10^9]范围,表示格子的数字。

输出

若无解,输出 -1

否则输出任意一个解,即一行 M 个正整数 p1, p2, · · · , pm,表示可以把初始表格的 pi列,放在新表格的第 i 列,以得到一个合法的表格。


样例输入

样例输入1:
3 3
-1 -1 -1
2 1 2
2 -1 1 


样例输入2:
2 2
1 2
2 1

样例输出

样例输出1:
2 3 1


样例输出2:
-1

提示


对于 20% 的数据,满足 1 ≤ N ≤ 8,1 ≤ M ≤ 8。



对于 60% 的数据,满足 1 ≤ N × M ≤ 2 × 10^3。



对于 100% 的数据,满足 1 ≤ N × M ≤ 10^5。

[提交][状态]