Lenny 有一个 n × m 正整数矩阵。他非常喜欢这个矩阵,因为矩阵的每一行都是按非降序排序的。出于同样的原因,他称这种整数矩阵很可爱。
有一天,当莱尼在学校时,他的弟弟正在他的房间里玩莱尼的矩阵。他删除了矩阵的一些条目并更改了一些列的顺序。当莱尼回到家时,他非常沮丧。现在莱尼想要恢复他的矩阵。
帮助他找到矩阵各列的顺序,以便可以填充矩阵中被删除的条目,从而再次获得一个可爱的矩阵。请注意,您可以使用任何整数填充矩阵的已擦除条目。
输入
输入的第一行包含两个正整数 n 和 m (1 ≤ n·m ≤ 105)。接下来的 n 行中的每一行都包含 m 个空格分隔的整数,表示矩阵。整数 -1 表示矩阵的已擦除条目。所有其他整数(每个整数都在 0 到 109 之间(包括 0 和 109))表示已填充的条目。
输出
如果不存在可能的列重新排序,则打印 -1。否则,输出应包含 m 个整数 p1、p2、...、pm,显示所寻求的列排列。因此,可爱矩阵的第一列将是初始矩阵的第 p1 列,可爱矩阵的第二列将是初始矩阵的第 p2 列,依此类推。
示例
输入 #1
3 3 1 -1 -1 1 2 1 2 -1 1
输出 #1
3 1 2
输入 #2
2 3 1 2 2 2 5 4
输出 #2
1 3 2
输入 #3
2 3 1 2 3 3 2 1
输出 #3
-1