你正在瀏覽一個線上收藏，其中有 $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\le500$; $1\le m\le5$）。

接下來 $n$ 行中的第 $i$ 行包含 $m$ 個整數 $a_{i,1},a_{i,2},\ldots,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。

• 點擊「右」。指標移到物品 2 右方最近、且滿足唯一有效條件 $(3,4)$ 的物品，也就是物品 5。（改為點擊「左」也可以。）

從物品 8 移到物品 3 的一種最快方法如下：

• 新增篩選條件 $(3,4)$。由於物品 8 不滿足此條件，指標移到物品 8 右方最近、且參數 3 的值等於 4 的物品，也就是物品 2。

• 移除篩選條件 $(3,4)$。指標停在物品 2。

• 點擊「右」。由於集合中沒有篩選條件，指標移到物品 3。