Farmer John 的农场可以表示为一张有向带权图，其中道路（边）连接不同的节点，每条边的权值为沿这条道路行进所需的时间。每天，Bessie 都喜欢从牛棚（位于节点 $1$）出发，恰好经过 $K$ 条道路到达田地（位于节点 $N$），并希望在这一限制下尽快到达田地。然而，从某个时刻开始，道路不再得到维护，它们一条接一条地损坏，变得无法通行。请帮助 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$ 个整数。第 $i$ 行的第 $j$ 个整数为 $w_{ij}$（$1\le w_{ij}\le 10^8$）。

随后有 $N^2$ 行，每行包含两个整数 $i$ 和 $j$（$1\le i,j\le N$）。每一对整数恰好出现一次。

输出格式

输出恰好 $N^2$ 行，分别为每次删除后恰好经过 $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