Vous parcourez une collection en ligne de $n$ objets numérotés de $1$ à $n$ et disposés en cercle. L'objet à droite de chaque objet $i$ est l'objet $i+1$, et l'objet à droite de l'objet $n$ est l'objet $1$. De même, l'objet à gauche de chaque objet $i$ est l'objet $i-1$, et l'objet à gauche de l'objet $1$ est l'objet $n$.

Les objets possèdent $m$ paramètres numérotés de $1$ à $m$. La valeur du paramètre $j$ de l'objet $i$ est un entier $a_{i,j}$.

Pendant la navigation, à tout instant, un pointeur désigne un objet, appelé l'objet courant.

De plus, vous pouvez gérer un ensemble de conditions de filtrage. Chaque condition est une paire $(j,v)$, signifiant que le $j$-ème paramètre de l'objet doit être égal à $v$. L'objet courant satisfait toujours toutes les conditions de l'ensemble.

Pour parcourir la collection, vous pouvez effectuer des opérations. Chaque opération doit être de l'un des quatre types suivants :

• Cliquer sur « droite ». Le pointeur se déplace vers l'objet le plus proche à droite de l'objet courant qui satisfait toutes les conditions de filtrage. En particulier, si l'objet courant est le seul de ce type, le pointeur ne bouge pas.

• Cliquer sur « gauche ». De même, le pointeur se déplace vers l'objet le plus proche à gauche de l'objet courant qui satisfait toutes les conditions de filtrage, et reste sur place si l'objet courant est le seul de ce type.

• Ajouter une nouvelle condition de filtrage $(j,v)$, pour certains entiers $j$ et $v$. Si l'objet courant satisfait cette condition, le pointeur ne bouge pas. Sinon, il se déplace vers l'objet le plus proche à droite de l'objet courant qui satisfait toutes les conditions de filtrage, y compris la nouvelle. S'il n'existe aucun objet de ce type, l'opération est illégale et ne peut pas être effectuée.

• Supprimer de l'ensemble une condition de filtrage $(j,v)$ quelconque. Le pointeur ne bouge pas.

Pour chaque paire ordonnée d'objets $(i,j)$, répondez à la question suivante :

• Si vous commencez à parcourir la collection avec le pointeur sur l'objet $i$ et sans aucune condition de filtrage dans l'ensemble, quel est le nombre minimal d'opérations nécessaire pour déplacer le pointeur vers l'objet $j$ ? L'ensemble des conditions de filtrage peut être quelconque à la fin.

Entrée

La première ligne contient deux entiers $n$ et $m$, indiquant le nombre d'objets de la collection et le nombre de paramètres de chaque objet ($2\le n\le500$; $1\le m\le5$).

La $i$-ème des $n$ lignes suivantes contient $m$ entiers $a_{i,1},a_{i,2},\ldots,a_{i,m}$, indiquant les valeurs des paramètres de l'objet $i$ ($1\le a_{i,j}\le n$).

Sortie

Affichez $n$ lignes contenant chacune $n$ entiers.

Le $j$-ème entier de la $i$-ème ligne doit être égal au nombre minimal d'opérations nécessaire pour déplacer le pointeur de l'objet $i$ vers l'objet $j$, en commençant avec un ensemble vide de conditions de filtrage.

Exemples

Entrée 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

Sortie 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

Remarque

Dans l'exemple, voici une façon la plus rapide possible de passer de l'objet 2 à l'objet 5 :

• Ajouter une nouvelle condition de filtrage $(3,4)$. Puisque le paramètre 3 de l'objet 2 vaut effectivement 4, le pointeur reste sur l'objet 2.

• Cliquer sur « droite ». Le pointeur se déplace vers l'objet le plus proche à droite de l'objet 2 satisfaisant l'unique condition active $(3,4)$. Il s'agit de l'objet 5. (Cliquer sur « gauche » à la place fonctionne également.)

Voici une façon la plus rapide possible de passer de l'objet 8 à l'objet 3 :

• Ajouter une nouvelle condition de filtrage $(3,4)$. Puisque l'objet 8 ne satisfait pas cette condition, le pointeur se déplace vers l'objet le plus proche à droite de l'objet 8 dont le paramètre 3 vaut 4. Il s'agit de l'objet 2.

• Supprimer la condition de filtrage $(3,4)$. Le pointeur reste sur l'objet 2.

• Cliquer sur « droite ». Puisque l'ensemble ne contient aucune condition de filtrage, le pointeur se déplace vers l'objet 3.