你正在浏览一个包含 $n$ 个项目的在线集合，这些项目编号为 $1$ 到 $n$，排列在一个圆环上。每个项目 $i$ 右侧的项目是 $i+1$，项目 $n$ 右侧的项目是 $1$。类似地，每个项目 $i$ 左侧的项目是 $i-1$，项目 $1$ 左侧的项目是 $n$。

这些项目具有 $m$ 个参数，编号为 $1$ 到 $m$。项目 $i$ 的第 $j$ 个参数的值是一个整数 $a_{i,j}$。在浏览时，任何时刻都有一个指向某个项目的指针，称为当前项目。此外，你可以管理一组过滤条件。每个条件是一个二元组 $(j, v)$，表示项目的第 $j$ 个参数必须等于 $v$。当前项目始终满足集合中的所有条件。

为了浏览集合，你可以执行操作。每个操作必须是以下四种类型之一：

• 点击“右移”。指针移动到当前项目右侧满足所有过滤条件的最近项目。特别地，如果当前项目是唯一满足条件的项，指针不移动。
• 点击“左移”。类似地，指针移动到当前项目左侧满足所有过滤条件的最近项目；如果当前项目是唯一满足条件的项，指针保持在原位。
• 添加一个新的过滤条件 $(j, v)$，其中 $j$ 和 $v$ 为整数。如果当前项目满足此条件，指针不移动。否则，指针移动到当前项目右侧满足所有过滤条件（包括新添加的条件）的最近项目。如果不存在这样的项目，则该操作非法，无法执行。
• 从集合中移除任意过滤条件 $(j, v)$。指针不移动。

对于每一对有序项目 $(i, j)$，回答以下问题：

• 如果你开始浏览时指针指向项目 $i$，且集合中没有任何过滤条件，那么将指针移动到项目 $j$ 所需的最少操作次数是多少？结束时过滤条件集合可以是任意状态。

输入格式

第一行包含两个整数 $n$ 和 $m$，表示集合中的项目数量和每个项目拥有的参数数量 ($2 \le n \le 500; 1 \le m \le 5$)。

接下来的 $n$ 行中，第 $i$ 行包含 $m$ 个整数 $a_{i,1}, a_{i,2}, \dots, a_{i,m}$，表示项目 $i$ 的参数值 ($1 \le a_{i,j} \le n$)。

输出格式

输出 $n$ 行，每行包含 $n$ 个整数。

在第 $i$ 行中，第 $j$ 个整数必须等于从项目 $i$ 移动到项目 $j$ 所需的最少操作次数，开始时过滤条件集合为空。

样例

样例输入 1

9 3
5 3 7
5 3 4
5 3 7
5 3 2
5 3 4
5 3 7
2 3 7
5 3 7
2 3 7

样例输出 1

0 1 2 1 2 3 1 2 1
1 0 1 1 2 2 1 3 2
2 1 0 1 1 2 1 3 2
3 2 1 0 1 1 1 3 2
3 2 2 1 0 1 1 3 2
3 1 2 1 1 0 1 2 2
2 1 3 1 2 1 0 1 2
2 1 3 1 2 2 1 0 1
1 1 3 1 2 3 2 1 0

说明

在样例测试中，以下是从项目 2 移动到项目 5 的一种可能的最快方式：

• 添加一个新的过滤条件 $(3, 4)$。由于项目 2 的第 3 个参数值确实等于 4，指针保持在项目 2。
• 点击“右移”。指针移动到当前项目右侧满足唯一激活条件 $(3, 4)$ 的最近项目。该项目是项目 5。（点击“左移”同样有效。）

以下是从项目 8 移动到项目 3 的一种可能的最快方式：

• 添加一个新的过滤条件 $(3, 4)$。由于项目 8 不满足此条件，指针移动到当前项目右侧第 3 个参数值为 4 的最近项目。该项目是项目 2。
• 移除过滤条件 $(3, 4)$。指针保持在项目 2。
• 点击“右移”。由于集合中没有过滤条件，指针移动到项目 3。