该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

你说的对，但是被我 Hack 了

时间限制：2s

空间限制：256MB

题目描述

考虑以下问题：

现有 $n$ 行 $m$ 列的矩阵，每个格子中写有一个数字 $a_{ij}$ 。

若两个 相邻 的格子 $x,y$ 上的数字满足：格子 $x$ 中的数字 小于 $y$ 中的数字，则 $x$ 可以走一步到达 $y$ 。

• 相邻指的是两个格子位于同一行，且列号相差 $1$ ，或处于同一列，且行号相差 $1$ 。特别地，若相邻的格子数字 相同，则它们 互相不可达 。

从左上角点 $(1,1)$ 出发，设一条路径的长度是路径中经过点的个数减 $1$。求所有从 $(1,1)$ 出发的路径中，路径长度的最大值。

（来源：南师大 2021 年 11 月程序设计竞赛 E 题）

例如，对于 $3 \times 3$ 的矩阵

1 100 10000

15 140 10000

30 -50 0

答案就是 $3$，其中一条可行路径如下：$(1,1)\to (2,1)\to (2,2)\to (2,3)$，分别经过 $1\to 15\to 140\to 10000$。

现在， pzr 打算使用广度优先搜索算法解决这个问题。算法流程可描述如下：

该算法虽然在随机数据上表现较好，但在极端数据下表现不佳。

程序的效率大致与循环（外层 while 循环 和内层 for 循环）的总执行次数有关，请造一组 Hack 数据，使得网格的大小是给定的 $n \times m$，且循环总执行次数 $cnt$ 达到 $limit=19260817$ 次以上。具体来说，将采用以下方法检查循环总执行次数。

输入格式

矩阵的大小 $n,m$。

输出格式

共 $n$ 行，每行 $m$ 个数字，表示你构造的矩阵。

你需要保证矩阵的每个元素均为 $[1, n\times m]$ 之间的正整数。（但是，并不需要保证各元素不同）

循环次数将按照上述方式统计。如果超过 $limit$，则认为 Hack 成功。

如果有多种可行的构造方法，输出任意一种可行的即可。

样例输入1

10 10

样例输出1

1 2 3 4 5 6 7 8 9 10 
11 12 13 14 15 16 17 18 19 20 
21 22 23 24 25 26 27 28 29 30 
31 32 33 34 35 36 37 38 39 40 
41 42 43 44 45 46 47 48 49 50 
51 52 53 54 55 56 57 58 59 60 
61 62 63 64 65 66 67 68 69 70 
71 72 73 74 75 76 77 78 79 80 
81 82 83 84 85 86 87 88 89 90 
91 92 93 94 95 96 97 98 99 100

样例 1 解释

本测试点仅用于说明题意。$n$ 和 $m$ 不满足数据范围中的限定。

若按此方法构造，循环执行次数为 $cnt = 280$。

样例输入2

5000 5000

样例输出2

1 2 3 ... 5000
5001 5002 ... 10000
...  ...
...  ... 25000000

样例 2 解释

上面给出了一种构造方法，按行优先顺序依次摆放 $1,2,\cdots 5000\times 5000$，循环总运行次数为 74990000。

对于 n, m 更小的情况，可能需要其他的构造方法。

数据范围与约定

共包含三个测试点，前两个测试点 30 分，最后一个测试点 40 分。

第一组测试点满足 $n=m=3000$。

第二组测试点满足 $n=400, m =500$。

第三组测试点满足 $n=m=80$。