Você está explorando uma coleção on-line de $n$ itens numerados de $1$ a $n$, dispostos em um círculo. À direita de cada item $i$ está o item $i+1$, e à direita do item $n$ está o item $1$. Analogamente, à esquerda de cada item $i$ está o item $i-1$, e à esquerda do item $1$ está o item $n$.

Os itens têm $m$ parâmetros numerados de $1$ a $m$. O valor do parâmetro $j$ do item $i$ é um inteiro $a_{i,j}$.

Durante a exploração, a qualquer momento há um ponteiro apontando para algum item, chamado item atual.

Além disso, você pode gerenciar um conjunto de condições de filtragem. Cada condição é um par $(j,v)$, que significa que o $j$-ésimo parâmetro do item deve ser igual a $v$. O item atual sempre satisfaz todas as condições do conjunto.

Para explorar a coleção, você pode realizar operações. Cada operação deve ser de um dos quatro tipos a seguir:

• Clicar em “direita”. O ponteiro se move para o item mais próximo à direita do item atual que satisfaz todas as condições de filtragem. Em particular, se o item atual for o único que as satisfaz, o ponteiro não se move.

• Clicar em “esquerda”. Analogamente, o ponteiro se move para o item mais próximo à esquerda do item atual que satisfaz todas as condições de filtragem, e permanece no mesmo lugar se o item atual for o único que as satisfaz.

• Adicionar uma nova condição de filtragem $(j,v)$, para certos inteiros $j$ e $v$. Se o item atual satisfizer essa condição, o ponteiro não se move. Caso contrário, move-se para o item mais próximo à direita do item atual que satisfaz todas as condições de filtragem, incluindo a nova. Se não existir tal item, a operação é ilegal e não pode ser realizada.

• Remover do conjunto qualquer condição de filtragem $(j,v)$. O ponteiro não se move.

Para cada par ordenado de itens $(i,j)$, responda à seguinte pergunta:

• Se você começar a explorar com o ponteiro no item $i$ e sem condições de filtragem no conjunto, qual é o menor número de operações necessário para movê-lo para o item $j$? O conjunto de condições de filtragem pode ser qualquer um ao final.

Entrada

A primeira linha contém dois inteiros $n$ e $m$, indicando o número de itens da coleção e o número de parâmetros de cada item ($2\le n\le500$; $1\le m\le5$).

A $i$-ésima das próximas $n$ linhas contém $m$ inteiros $a_{i,1},a_{i,2},\ldots,a_{i,m}$, indicando os valores dos parâmetros do item $i$ ($1\le a_{i,j}\le n$).

Saída

Imprima $n$ linhas contendo $n$ inteiros cada.

Na $i$-ésima linha, o $j$-ésimo inteiro deve ser igual ao menor número de operações necessário para mover o ponteiro do item $i$ para o item $j$, começando com um conjunto vazio de condições de filtragem.

Exemplos

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

Saída 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

No exemplo, uma possível maneira mais rápida de ir do item 2 ao item 5 é a seguinte:

• Adicione uma nova condição de filtragem $(3,4)$. Como o parâmetro 3 do item 2 realmente tem valor 4, o ponteiro permanece no item 2.

• Clique em “direita”. O ponteiro se move para o item mais próximo à direita do item 2 que satisfaz a única condição ativa $(3,4)$. Esse é o item 5. (Clicar em “esquerda” em vez disso também funciona.)

Uma possível maneira mais rápida de ir do item 8 ao item 3 é a seguinte:

• Adicione uma nova condição de filtragem $(3,4)$. Como o item 8 não satisfaz essa condição, o ponteiro se move para o item mais próximo à direita do item 8 cujo parâmetro 3 tem valor 4. Esse é o item 2.

• Remova a condição de filtragem $(3,4)$. O ponteiro permanece no item 2.

• Clique em “direita”. Como não há condições de filtragem no conjunto, o ponteiro se move para o item 3.