Problem1462--PIPI的弹珠箱子

1462: PIPI的弹珠箱子

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 403  Solved: 196
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI在回寝室的路上捡到了一个箱子,箱子的顶部和底部都是开着的,箱子内部可以看成一个n*m的二维网格。
箱子内部的每个单元格都有一个对角线挡板,跨过单元格的两个角,可以将弹珠导向左侧或者右侧。
弹珠导向右侧的挡板跨过左上角和右下角,在网格中用 1 表示。
弹珠导向左侧的挡板跨过右上角和左下角,在网格中用 -1 表示。
在箱子每一列的顶端各放一颗弹珠。每颗弹珠都可能卡在箱子里或从底部掉出来。如果弹珠恰好卡在两块挡板之间的 "V" 形图案,或者被一块挡导向到箱子的任意一侧边上,就会卡住。
现在PIPI想知道从顶部每一列放入的弹珠会从底部哪一列出来?


Input

第一行输入两个整数n,m,分别表示箱子的行数和列数,1<=n,m<=1000
接下来n行,每行m个整数,该整数只会等于-1或者1,表示每个格子对角线的方向

Output

输出m个整数,分别表示从第1列到第m列放入的小球会从哪一列落下。如果中途被卡住输出-1。

Sample Input

5 5
1 1 1 -1 -1
1 1 1 -1 -1
-1 -1 -1 1 1
1 1 1 1 -1
-1 -1 -1 -1 -1
​

Sample Output

1 -1 -1 -1 -1

Source/Category