Browsing the Collection

You are browsing an online collection of $n$ items numbered from $1$ to $n$ arranged on a circle. The item to the right of each item $i$ is item $i + 1$, and the item to the right of item $n$ is item $1$. Similarly, the item to the left of each item $i$ is item $i - 1$, and the item to the left of item $1$ is item $n$.

The items have $m$ parameters numbered from $1$ to $m$. The value of parameter $j$ for item $i$ is an integer $a_{i, j}$.

While you are browsing, the pointer is always directed at some item, called the current item. You can also manage a set of filtering conditions. Each condition is a pair $(j, v)$, meaning that the $j$-th parameter of the item must be equal to $v$. The current item always satisfies all conditions in the set.

To browse the collection, you perform operations. Each operation must be one of the following four kinds:

• Click right. The pointer moves to the closest item to the right of the current item that satisfies all filtering conditions. If the current item is the only such item, the pointer does not move.
• Click left. The pointer moves to the closest item to the left of the current item that satisfies all filtering conditions. If the current item is the only such item, the pointer does not move.
• Add a new filtering condition $(j, v)$. If the current item satisfies this condition, the pointer does not move. Otherwise, the pointer moves to the closest item to the right of the current item that satisfies all filtering conditions, including the new one. If there is no such item, the operation is illegal and cannot be performed.
• Remove any filtering condition $(j, v)$ from the set. The pointer does not move.

For each ordered pair of items $(i, j)$, answer the following question: if you start browsing with the pointer at item $i$ and with no filtering conditions in the set, what is the smallest number of operations needed to move the pointer to item $j$? The set of filtering conditions may be arbitrary at the end.

The first line contains two integers $n$ and $m$, the number of items and the number of parameters per item ($2 \le n \le 500$; $1 \le m \le 5$).

The $i$-th of the next $n$ lines contains $m$ integers $a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$, the parameter values of item $i$ ($1 \le a_{i, j} \le n$).

Print $n$ lines with $n$ integers each. In the $i$-th line, the $j$-th integer is the smallest number of operations required to move the pointer from item $i$ to item $j$, starting with an empty set of filtering conditions.

In the example test, one fastest way to move from item $2$ to item $5$ is:

• Add the filtering condition $(3, 4)$. Item $2$ has parameter $3$ equal to $4$, so the pointer stays at item $2$.
• Click right. The pointer moves to the closest item to the right of item $2$ that satisfies the only active condition $(3, 4)$. This item is item $5$. (Clicking left works as well.)

One fastest way to move from item $8$ to item $3$ is:

• Add the filtering condition $(3, 4)$. Item $8$ does not satisfy it, so the pointer moves to the closest item to the right of item $8$ with parameter $3$ equal to $4$. This item is item $2$.
• Remove the filtering condition $(3, 4)$. The pointer stays at item $2$.
• Click right. With no filtering conditions, the pointer moves to item $3$.