La granja de Farmer John puede representarse como un grafo dirigido ponderado, con carreteras (aristas) que conectan distintos nodos, donde el peso de cada arista es el tiempo necesario para recorrer la carretera. Cada día, a Bessie le gusta viajar del granero (situado en el nodo $1$) a los campos (situados en el nodo $N$) recorriendo exactamente $K$ carreteras, y quiere llegar a los campos lo más rápido posible bajo esta restricción. Sin embargo, en cierto momento las carreteras dejan de recibir mantenimiento y, una a una, empiezan a deteriorarse hasta volverse intransitables. ¡Ayuda a Bessie a encontrar el camino más corto del granero a los campos en cada momento!

Formalmente, empezamos con un grafo dirigido completo y ponderado de $N$ vértices ($1\le N\le 300$) con $N^2$ aristas: una arista por cada par $(i, j)$ con $1 \le i, j \le N$ (observa que hay $N$ bucles). Después de cada eliminación, imprime el peso mínimo de un camino de $1$ a $N$ que recorra exactamente $K$ aristas, no necesariamente distintas ($2\le K\le 8$). Observa que, después de la eliminación número $i$, quedan $N^2-i$ aristas en el grafo.

El peso de un camino se define como la suma de los pesos de todas sus aristas. Observa que un camino puede contener la misma arista y el mismo vértice varias veces, incluidos los vértices $1$ y $N$.

Entrada

La primera línea contiene $N$ y $K$.

Las siguientes $N$ líneas contienen $N$ enteros cada una. El entero número $j$ de la línea número $i$ es $w_{ij}$ ($1\le w_{ij}\le 10^8$).

A continuación aparecen $N^2$ líneas adicionales, cada una con dos enteros $i$ y $j$ ($1\le i,j\le N$). Cada par de enteros aparece exactamente una vez.

Salida

Imprime exactamente $N^2$ líneas, con el peso mínimo de un camino de $K$ aristas después de cada eliminación. Si no existe ningún camino de $K$ aristas, imprime $-1$.

Ejemplos

Entrada 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

Salida 1

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

Nota

Después de la primera eliminación, el camino más corto de $4$ aristas es:

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

Después de la segunda eliminación, el camino más corto de $4$ aristas es:

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

Después de la tercera eliminación, el camino más corto de $4$ aristas es:

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

Después de seis eliminaciones, ya no existe ningún camino de $4$ aristas.

Subtareas

• Para $2\le T\le 14$, el caso de prueba $T$ cumple $K=\lfloor (T+3)/2\rfloor$.

Autor del problema: Benjamin Qi