La fattoria di Farmer John può essere rappresentata come un grafo diretto pesato, con strade (archi) che collegano nodi diversi, e il peso di ciascun arco pari al tempo necessario per percorrere la strada. Ogni giorno, a Bessie piace andare dal fienile (situato nel nodo $1$) ai campi (situati nel nodo $N$) percorrendo esattamente $K$ strade, e vuole raggiungere i campi il più rapidamente possibile rispettando questo vincolo. Tuttavia, a un certo punto le strade non vengono più mantenute e, una dopo l'altra, iniziano a deteriorarsi, diventando impraticabili. Aiuta Bessie a trovare il percorso più breve dal fienile ai campi in ogni istante!

Formalmente, iniziamo con un grafo diretto completo pesato su $N$ vertici ($1\le N\le 300$) con $N^2$ archi: un arco per ogni coppia $(i, j)$ con $1 \le i, j \le N$ (nota che ci sono $N$ cappi). Dopo ogni rimozione, stampa il peso minimo di un qualsiasi percorso da $1$ a $N$ che attraversi esattamente $K$ archi (non necessariamente distinti) ($2\le K\le 8$). Nota che, dopo la $i$-esima rimozione, nel grafo rimangono $N^2-i$ archi.

Il peso di un percorso è definito come la somma dei pesi di tutti gli archi del percorso. Nota che un percorso può contenere più volte lo stesso arco e più volte lo stesso vertice, compresi i vertici $1$ e $N$.

Input

La prima riga contiene $N$ e $K$.

Le successive $N$ righe contengono ciascuna $N$ interi. Il $j$-esimo intero della $i$-esima riga è $w_{ij}$ ($1\le w_{ij}\le 10^8$).

Seguono poi altre $N^2$ righe, ciascuna contenente due interi $i$ e $j$ ($1\le i,j\le N$). Ogni coppia di interi compare esattamente una volta.

Output

Esattamente $N^2$ righe, con il peso minimo di un percorso di $K$ archi dopo ogni rimozione. Se non esiste un percorso di $K$ archi, stampa $-1$.

Esempi

Input 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

Output 1

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

Spiegazione

Dopo la prima rimozione, il percorso più breve di $4$ archi è:

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

Dopo la seconda rimozione, il percorso più breve di $4$ archi è:

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

Dopo la terza rimozione, il percorso più breve di $4$ archi è:

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

Dopo sei rimozioni, non esiste più alcun percorso di $4$ archi.

Sottoproblemi

• Per $2\le T\le 14$, il caso di test $T$ soddisfa $K=\lfloor (T+3)/2\rfloor$.

Autore del problema: Benjamin Qi