UOJ Logo

NOI.AC

1S 512MB
统计

在一块平原上有一头大象。

平原被分成$n\times m$个格子。初始时大象位于$(1,1)$。每一秒,大象会移动到一个相邻的格子上(四连通),但不会移动到平原外面。由于你视力不好,你无法知道大象每次移动到哪个格子上。

你可以使用火球术来攻击地面。每次释放火球术,你可以攻击任意多个格子。每个格子只能被攻击一次。大象不能移动到被攻击过的格子上,如果大象相邻的格子都无法移动,那么它会停在原地不动。

你的目标是最后只剩下一个格子没有被火球术攻击过,然后你去那里活捉大象。在此之前,你必须保证你的火球术不会击中大象。由于大象的战斗力十分强大,只有在某些格子中你才能抓住大象。

然而,由于你魔法水平不高,在使用火球术前你需要进行蓄势。第一次蓄势的时间至少为$n+m$秒,接下来每次蓄势时间都要比上次长。蓄势时间必须是整数秒。你希望最小化最后一次的蓄势时间。

注意:每一秒大象先移动,接着你才会释放火球术。也就是说,如果你第一次的蓄势时间为$n+m$秒,那么大象已经移动了$n+m$次。

Input

第一行包含两个整数 $n,m$。

接下来 $n$ 行每行 $m$ 个数,每个数只能是 0 或 1。第 $i+1$ 行第 $j$ 列的数表示 在$(i,j)$这个格子中,你能否抓住大象(1 表示能,0 表示不能)。

Output

输出若干行,每行表示释放一次火球术。

每行第一个整数表示蓄势时间,接下来若干个整数表示攻击的格子,第 $i$ 行第 $j$ 列的格子编号为$(i-1)*m+j$。每行最后输出一个 0。

如果无解输出一行一个整数$-1$。

Examples

3 3
1 1 1
1 1 1
1 1 1
7 1 3 7 9 0
9 2 4 6 8 0

Notes

alt

特殊条件A:在所有格子中,你都能抓住大象。

特殊条件B:至少存在一个格子,你可以抓住大象。

对于每个测试点,如果这个测试点无解并且你判断对了,得5分。

如果这个测试点有解,记这个测试点最优策略的答案为$ans$:

如果你的答案$=ans$,得5分;

如果你的答案$\leq ans+2$,得4分;

如果你的答案$\leq ans+4$,得3分;

如果你的答案$\leq 2ans$,得2分;

如果你的答案$\leq 10^8$,得1分。

满足多个条件取最高分。