Farmę Farmer John można przedstawić jako skierowany graf ważony, w którym drogi (krawędzie) łączą różne wierzchołki, a waga każdej krawędzi jest czasem potrzebnym na przejazd daną drogą. Każdego dnia Bessie lubi przechodzić ze stodoły (znajdującej się w wierzchołku $1$) na pola (znajdujące się w wierzchołku $N$), pokonując dokładnie $K$ dróg, i chce dotrzeć na pola jak najszybciej przy tym ograniczeniu. Jednak w pewnym momencie drogi przestają być utrzymywane i kolejno ulegają zniszczeniu, stając się nieprzejezdne. Pomóż Bessie znaleźć najkrótszą trasę ze stodoły na pola w każdej chwili!

Formalnie, zaczynamy od pełnego skierowanego grafu ważonego o $N$ wierzchołkach ($1\le N\le 300$) i $N^2$ krawędziach: po jednej krawędzi dla każdej pary $(i, j)$ dla $1 \le i, j \le N$ (zauważ, że istnieje $N$ pętli). Po każdym usunięciu wypisz minimalną wagę dowolnej trasy z $1$ do $N$, która przechodzi przez dokładnie $K$ (niekoniecznie różnych) krawędzi ($2\le K\le 8$). Zauważ, że po $i$-tym usunięciu w grafie pozostaje $N^2-i$ krawędzi.

Waga trasy jest zdefiniowana jako suma wag wszystkich jej krawędzi. Zauważ, że trasa może wielokrotnie zawierać tę samą krawędź oraz ten sam wierzchołek, w tym wierzchołki $1$ i $N$.

Wejście

Pierwszy wiersz zawiera $N$ i $K$.

Każdy z następnych $N$ wierszy zawiera $N$ liczb całkowitych. $j$-ta liczba całkowita w $i$-tym wierszu to $w_{ij}$ ($1\le w_{ij}\le 10^8$).

Następnie występuje $N^2$ dodatkowych wierszy, każdy zawierający dwie liczby całkowite $i$ i $j$ ($1\le i,j\le N$). Każda para liczb całkowitych występuje dokładnie raz.

Wyjście

Wypisz dokładnie $N^2$ wierszy, zawierających minimalną wagę trasy o $K$ krawędziach po każdym usunięciu. Jeśli taka trasa nie istnieje, wypisz $-1$.

Przykład

Wejście 1

3 4
10 4 4
9 5 3
2 1 6
3 1
2 3
2 1
3 2
2 2
1 3
3 3
1 1
1 2

Wyjście 1

11
18
22
22
22
-1
-1
-1
-1

Uwagi

Po pierwszym usunięciu najkrótsza trasa o $4$ krawędziach to:

1 -> 2 -> 3 -> 2 -> 3

Po drugim usunięciu najkrótsza trasa o $4$ krawędziach to:

1 -> 3 -> 2 -> 1 -> 3

Po trzecim usunięciu najkrótsza trasa o $4$ krawędziach to:

1 -> 3 -> 3 -> 3 -> 3

Po sześciu usunięciach nie istnieje już trasa o $4$ krawędziach.

Podzadania

• Dla $2\le T\le 14$ test $T$ spełnia $K=\lfloor (T+3)/2\rfloor$.

Autor zadania: Benjamin Qi