← 返回题目列表

Codeforces · 358/E

E. 迪玛和踢

中文机器翻译题面 查看原题

迪马是个好人。事实上,他很棒。但一切美好的事情都会结束……

Seryozha 只会踢 Dima 几次。因此,他将房间划分为单位方块。现在房间是一个由单位正方形组成的 n × m 矩形。

一开始,Seryozha 将 Dima 放在某个正方形的中心。然后他开始踢迪马(众所周知,他至少踢过迪马一次)。每次迪马被踢时,他都会飞起来并移动到四个方向之一(上、左、右、下)。 Dima 每次移动都会在相应方向上传递 k (k > 1) 个长度单位。谢廖扎真的很善良,所以他踢迪玛的方式使迪玛永远不会碰到墙壁(换句话说,迪玛永远不会离开房间的空间)。 Seryozha 也是动态角色,因此 Dima 永远不会在同一段上方飞行,连接一对相邻的方块两次。

谢廖扎踢了迪马很长时间,但迪马并没有报复心——迪马写道。迪马标记了他停留或飞行的所有方格。由于踢,Dima 不记得 k 值,所以他要求你找到与 Dima 的记录匹配的所有可能值。

输入

第一行包含 n 和 m (1 ≤ n, m ≤ 103) — 房间的大小。

接下来的 n 行,每行包含 m 个数字 aij — Dima 的笔记:aij = 1,如果 Dima 停留在正方形 (i, j) 中或在其上方飞行。否则 aij = 0。

至少有一个 aij 等于 1。

输出

在一行中按升序打印所有 k (k > 1),这与 Dima 的注释相匹配。如果不存在这样的 k 并且 Dima 发明了这个故事,则打印 -1。

示例

输入 #1

5 5
1 1 1 1 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 1 1 1 1

输出 #1

2 4

输入 #2

7 7
0 0 1 1 1 0 0
0 0 1 0 1 0 0
1 1 1 1 1 1 1
1 0 1 0 1 0 1
1 1 1 1 1 1 1
0 0 1 0 1 0 0
0 0 1 1 1 0 0

输出 #2

2

输入 #3

3 3
1 1 1
1 1 1
1 1 1

输出 #3

-1

输入#4

4 4
1 1 1 1
0 0 0 0
0 0 0 0
0 0 0 0

输出#4

3

输入 #5

5 5
0 0 1 0 0
0 0 1 0 0
1 1 1 1 1
0 0 1 0 0
0 0 1 0 0

输出 #5

-1