你正喺度瀏覽一個網上收藏，入面有 $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。