#C30801. 深搜基础:扫地机器人

深搜基础:扫地机器人

Background背景

Mike同学在为扫地机器人设计一个在矩形区域中行走的算法,Mike是这样设计的:先把机器人放在出发点 (1,1) 点上,机器人在每个点上都会沿用如下的规则来判断下一个该去的点是哪里。规则:优先向右,如果向右不能走(比如:右侧出了矩形或者右侧扫过了)则尝试向下,向下不能走则尝试向左,向左不能走则尝试向上;直到所有的点都扫过。

Mike为了验证自己设计的算法是否正确,打算先模拟一下这个算法,每当机器人走过一个单元格时,会在单元格内标记一个数字,这个数字从 1 开始,每经过一个单元格数字会递增 1 ,直到所有的单元格都扫一遍,也就是所有的单元格都标记过数字,机器人会自动停止。 比如:如果机器人按照上面的规则,清扫一个 3×43 \times 4 大小的矩形区域,那么标记数字的结果如下图所示。

image

再比如:如果机器人按照上面的规则,清扫一个 5×55 \times 5 大小的矩形区域,那么标记数字的结果如下图所示。

image

请你帮助Mike设计一个程序,按照上面的规则,将一个 n×mn \times m 大小的矩形,标记一下数字,输出最终标记的结果。

Input输入

一行内有 2 个两个整数 n 和 m ,用空格隔开,分别代表矩形区域的行数(高)和列数(宽)。1 < n,m < 10。

Output输出

输出按题意机器人走过每个点之后,标记数字的结果,每个数字输出时场宽设置为 3。

Samples样例

3 4
  1  2  3  4
 10 11 12  5
  9  8  7  6

Limitation限制

1s, 1024KiB for each test case.