注意：本题的时间限制为 3 秒，比默认限制长 50%。

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$ 个整数。第 $i$ 行的第 $j$ 个整数为 $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

说明 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