Przeglądasz internetową kolekcję $n$ przedmiotów ponumerowanych od $1$ do $n$ i ułożonych na okręgu. Na prawo od każdego przedmiotu $i$ znajduje się przedmiot $i+1$, a na prawo od przedmiotu $n$ — przedmiot $1$. Podobnie na lewo od każdego przedmiotu $i$ znajduje się przedmiot $i-1$, a na lewo od przedmiotu $1$ — przedmiot $n$.

Przedmioty mają $m$ parametrów ponumerowanych od $1$ do $m$. Wartością parametru $j$ przedmiotu $i$ jest liczba całkowita $a_{i,j}$.

Podczas przeglądania w każdej chwili wskaźnik wskazuje pewien przedmiot, zwany bieżącym.

Możesz też zarządzać zbiorem warunków filtrowania. Każdy warunek jest parą $(j,v)$ oznaczającą, że $j$-ty parametr przedmiotu musi być równy $v$. Bieżący przedmiot zawsze spełnia wszystkie warunki w zbiorze.

Aby przeglądać kolekcję, możesz wykonywać operacje. Każda operacja musi być jednego z następujących czterech rodzajów:

• Kliknięcie „w prawo”. Wskaźnik przechodzi do najbliższego przedmiotu na prawo od bieżącego, który spełnia wszystkie warunki filtrowania. W szczególności jeśli bieżący przedmiot jest jedynym takim przedmiotem, wskaźnik się nie porusza.

• Kliknięcie „w lewo”. Analogicznie wskaźnik przechodzi do najbliższego przedmiotu na lewo od bieżącego, który spełnia wszystkie warunki filtrowania, i pozostaje w miejscu, jeśli bieżący przedmiot jest jedynym takim przedmiotem.

• Dodanie nowego warunku filtrowania $(j,v)$ dla pewnych liczb całkowitych $j$ i $v$. Jeśli bieżący przedmiot spełnia ten warunek, wskaźnik się nie porusza. W przeciwnym razie przechodzi do najbliższego przedmiotu na prawo od bieżącego, który spełnia wszystkie warunki filtrowania, łącznie z nowym. Jeśli taki przedmiot nie istnieje, operacja jest niedozwolona i nie można jej wykonać.

• Usunięcie ze zbioru dowolnego warunku filtrowania $(j,v)$. Wskaźnik się nie porusza.

Dla każdej uporządkowanej pary przedmiotów $(i,j)$ odpowiedz na następujące pytanie:

• Jeśli zaczynasz przeglądanie ze wskaźnikiem na przedmiocie $i$ i pustym zbiorem warunków filtrowania, jaka jest najmniejsza liczba operacji potrzebna do przeniesienia wskaźnika na przedmiot $j$? Końcowy zbiór warunków filtrowania może być dowolny.

Wejście

Pierwszy wiersz zawiera dwie liczby całkowite $n$ i $m$, oznaczające liczbę przedmiotów w kolekcji oraz liczbę parametrów każdego przedmiotu ($2\le n\le500$; $1\le m\le5$).

$i$-ty z kolejnych $n$ wierszy zawiera $m$ liczb całkowitych $a_{i,1},a_{i,2},\ldots,a_{i,m}$, oznaczających wartości parametrów przedmiotu $i$ ($1\le a_{i,j}\le n$).

Wyjście

Wypisz $n$ wierszy, każdy zawierający $n$ liczb całkowitych.

$j$-ta liczba w $i$-tym wierszu musi być równa najmniejszej liczbie operacji potrzebnej do przeniesienia wskaźnika z przedmiotu $i$ na przedmiot $j$, zaczynając z pustym zbiorem warunków filtrowania.

Przykład

Wejście 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

Wyjście 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

Uwagi

W przykładzie jeden z najszybszych sposobów przejścia z przedmiotu 2 do przedmiotu 5 jest następujący:

• Dodaj nowy warunek filtrowania $(3,4)$. Ponieważ parametr 3 przedmiotu 2 rzeczywiście ma wartość 4, wskaźnik pozostaje na przedmiocie 2.

• Kliknij „w prawo”. Wskaźnik przechodzi do najbliższego przedmiotu na prawo od przedmiotu 2, który spełnia jedyny aktywny warunek $(3,4)$. Jest to przedmiot 5. (Kliknięcie „w lewo” zamiast tego również działa.)

Oto jeden z najszybszych sposobów przejścia z przedmiotu 8 do przedmiotu 3:

• Dodaj nowy warunek filtrowania $(3,4)$. Ponieważ przedmiot 8 nie spełnia tego warunku, wskaźnik przechodzi do najbliższego przedmiotu na prawo od przedmiotu 8, którego parametr 3 ma wartość 4. Jest to przedmiot 2.

• Usuń warunek filtrowania $(3,4)$. Wskaźnik pozostaje na przedmiocie 2.

• Kliknij „w prawo”. Ponieważ zbiór nie zawiera warunków filtrowania, wskaźnik przechodzi do przedmiotu 3.