A fazenda de Farmer John pode ser representada como um grafo direcionado e ponderado, com estradas (arestas) ligando diferentes nós, sendo o peso de cada aresta o tempo necessário para percorrer a estrada. Todos os dias, Bessie gosta de ir do celeiro (localizado no nó $1$) até os campos (localizados no nó $N$), percorrendo exatamente $K$ estradas, e quer chegar aos campos o mais rapidamente possível sob essa restrição. Porém, em algum momento, as estradas deixam de receber manutenção e, uma a uma, começam a se deteriorar, tornando-se intransitáveis. Ajude Bessie a encontrar o caminho mais curto do celeiro até os campos em todos os momentos!

Formalmente, começamos com um grafo direcionado completo e ponderado com $N$ vértices ($1\le N\le 300$) e $N^2$ arestas: uma aresta para cada par $(i, j)$ com $1 \le i, j \le N$ (observe que existem $N$ laços). Após cada remoção, imprima o peso mínimo de qualquer caminho de $1$ até $N$ que percorra exatamente $K$ arestas, não necessariamente distintas ($2\le K\le 8$). Observe que, após a $i$-ésima remoção, restam $N^2-i$ arestas no grafo.

O peso de um caminho é definido como a soma dos pesos de todas as arestas do caminho. Observe que um caminho pode repetir a mesma aresta e o mesmo vértice, incluindo os vértices $1$ e $N$.

Entrada

A primeira linha contém $N$ e $K$.

As próximas $N$ linhas contêm $N$ inteiros cada. O $j$-ésimo inteiro da $i$-ésima linha é $w_{ij}$ ($1\le w_{ij}\le 10^8$).

Em seguida, vêm $N^2$ linhas adicionais, cada uma contendo dois inteiros $i$ e $j$ ($1\le i,j\le N$). Cada par de inteiros aparece exatamente uma vez.

Saída

Exatamente $N^2$ linhas, com o peso mínimo de um caminho com $K$ arestas após cada remoção. Se não existir um caminho com $K$ arestas, imprima $-1$.

Exemplos

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

Saída 1

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

Explicação

Após a primeira remoção, o caminho mais curto com $4$ arestas é:

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

Após a segunda remoção, o caminho mais curto com $4$ arestas é:

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

Após a terceira remoção, o caminho mais curto com $4$ arestas é:

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

Após seis remoções, não existe mais um caminho com $4$ arestas.

Subtarefas

• Para $2\le T\le 14$, o caso de teste $T$ satisfaz $K=\lfloor (T+3)/2\rfloor$.

Autor do problema: Benjamin Qi