Ферму Farmer John можно представить в виде взвешенного ориентированного графа, в котором дороги (рёбра) соединяют различные вершины, а вес каждого ребра равен времени, необходимому для проезда по дороге. Каждый день Bessie любит добираться из сарая (расположенного в вершине $1$) на поля (расположенные в вершине $N$), проезжая ровно по $K$ дорогам, и хочет при этом ограничении добраться до полей как можно быстрее. Однако в какой-то момент дороги перестают обслуживать, и они одна за другой начинают разрушаться и становятся непроезжими. Помогите Bessie найти кратчайший путь из сарая на поля в каждый момент времени!

Формально, изначально дан полный взвешенный ориентированный граф на $N$ вершинах ($1\le N\le 300$) с $N^2$ рёбрами: по одному ребру для каждой пары $(i, j)$, где $1 \le i, j \le N$ (обратите внимание, что есть $N$ петель). После каждого удаления выведите минимальный вес пути из $1$ в $N$, проходящего ровно по $K$ (не обязательно различным) рёбрам ($2\le K\le 8$). Обратите внимание, что после $i$-го удаления в графе остаётся $N^2-i$ рёбер.

Вес пути определяется как сумма весов всех его рёбер. Обратите внимание, что путь может несколько раз содержать одно и то же ребро и одну и ту же вершину, включая вершины $1$ и $N$.

Входные данные

Первая строка содержит $N$ и $K$.

Следующие $N$ строк содержат по $N$ целых чисел. $j$-е число в $i$-й строке равно $w_{ij}$ ($1\le w_{ij}\le 10^8$).

Затем следуют ещё $N^2$ строк, каждая из которых содержит два целых числа $i$ и $j$ ($1\le i,j\le N$). Каждая пара целых чисел встречается ровно один раз.

Выходные данные

Ровно $N^2$ строк: минимальный вес пути из $K$ рёбер после каждого удаления. Если пути из $K$ рёбер не существует, выведите $-1$.

Примеры

Входные данные 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

Выходные данные 1

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

Примечание

После первого удаления кратчайший путь из $4$ рёбер:

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

После второго удаления кратчайший путь из $4$ рёбер:

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

После третьего удаления кратчайший путь из $4$ рёбер:

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

После шести удалений пути из $4$ рёбер больше не существует.

Подзадачи

• Для $2\le T\le 14$ в тесте $T$ выполняется $K=\lfloor (T+3)/2\rfloor$.

Автор задачи: Benjamin Qi