Estás explorando una colección en línea de $n$ objetos numerados del $1$ al $n$, dispuestos en un círculo. A la derecha de cada objeto $i$ está el objeto $i+1$, y a la derecha del objeto $n$ está el objeto $1$. Del mismo modo, a la izquierda de cada objeto $i$ está el objeto $i-1$, y a la izquierda del objeto $1$ está el objeto $n$.

Los objetos tienen $m$ parámetros numerados del $1$ al $m$. El valor del parámetro $j$ del objeto $i$ es un entero $a_{i,j}$.

Mientras exploras, en todo momento hay un puntero que apunta a un objeto, llamado objeto actual.

Además, puedes gestionar un conjunto de condiciones de filtrado. Cada condición es un par $(j,v)$, que significa que el parámetro $j$ del objeto debe ser igual a $v$. El objeto actual siempre satisface todas las condiciones del conjunto.

Para explorar la colección puedes realizar operaciones. Cada operación debe ser de uno de los cuatro tipos siguientes:

• Pulsar «derecha». El puntero se mueve al objeto más cercano a la derecha del objeto actual que satisfaga todas las condiciones de filtrado. En particular, si el objeto actual es el único que las satisface, el puntero no se mueve.

• Pulsar «izquierda». Del mismo modo, el puntero se mueve al objeto más cercano a la izquierda del objeto actual que satisfaga todas las condiciones de filtrado, y permanece en su lugar si el objeto actual es el único que las satisface.

• Añadir una nueva condición de filtrado $(j,v)$, para ciertos enteros $j$ y $v$. Si el objeto actual satisface esta condición, el puntero no se mueve. En caso contrario, se mueve al objeto más cercano a la derecha del objeto actual que satisfaga todas las condiciones de filtrado, incluida la nueva. Si no existe tal objeto, la operación es ilegal y no puede realizarse.

• Eliminar del conjunto cualquier condición de filtrado $(j,v)$. El puntero no se mueve.

Para cada par ordenado de objetos $(i,j)$, responde a la siguiente pregunta:

• Si empiezas a explorar con el puntero en el objeto $i$ y sin condiciones de filtrado en el conjunto, ¿cuál es el menor número de operaciones que necesitas para moverlo al objeto $j$? El conjunto de condiciones de filtrado al terminar puede ser cualquiera.

Entrada

La primera línea contiene dos enteros $n$ y $m$, que indican el número de objetos de la colección y el número de parámetros de cada objeto ($2\le n\le500$; $1\le m\le5$).

La línea $i$ de las siguientes $n$ líneas contiene $m$ enteros $a_{i,1},a_{i,2},\ldots,a_{i,m}$, que indican los valores de los parámetros del objeto $i$ ($1\le a_{i,j}\le n$).

Salida

Imprime $n$ líneas, cada una con $n$ enteros.

En la línea $i$, el entero $j$ debe ser igual al menor número de operaciones necesarias para mover el puntero del objeto $i$ al objeto $j$, empezando con un conjunto vacío de condiciones de filtrado.

Ejemplos

Entrada 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

Salida 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

Nota

En el ejemplo, una posible forma más rápida de ir del objeto 2 al objeto 5 es la siguiente:

• Añadir una nueva condición de filtrado $(3,4)$. Como el parámetro 3 del objeto 2 efectivamente vale 4, el puntero permanece en el objeto 2.

• Pulsar «derecha». El puntero se mueve al objeto más cercano a la derecha del objeto 2 que satisface la única condición activa $(3,4)$. Este es el objeto 5. (Pulsar «izquierda» en su lugar también funciona.)

Una posible forma más rápida de ir del objeto 8 al objeto 3 es la siguiente:

• Añadir una nueva condición de filtrado $(3,4)$. Como el objeto 8 no satisface esta condición, el puntero se mueve al objeto más cercano a la derecha del objeto 8 cuyo parámetro 3 vale 4. Este es el objeto 2.

• Eliminar la condición de filtrado $(3,4)$. El puntero permanece en el objeto 2.

• Pulsar «derecha». Como no hay condiciones de filtrado en el conjunto, el puntero se mueve al objeto 3.