题目描述

Aki 设计了一个传送网络：共有 $N$ 个传送点，编号为 $1,2,\ldots,N$。
对任意一对 $(i,j)$（$1\le i,j\le N$），都存在一条从 $i$ 到 $j$ 的有向边，其代价为 $C_{i,j}$。

Aki 会选择一个起点 $s$，并且恰好移动 $K$ 次（每次沿一条有向边移动到下一个点）。移动序列记为

要求满足 $v_0=v_K=s$。该移动的总代价为

请你对每个 $s=1,2,\ldots,N$，求出从 $s$ 出发恰好走 $K$ 次并回到 $s$ 的最小可能总代价。

输入格式

第一行两个整数 $N,K$。
接下来 $N$ 行，每行 $N$ 个整数，第 $i$ 行第 $j$ 个数为 $C_{i,j}$。

同时，输入中数据规模满足：

• $1\le N\le 100$
• $1\le K\le 10^9$
• $0\le C_{i,j}\le 10^9$

输出格式

输出 $N$ 行。
第 $i$ 行输出起点 $s=i$ 时的答案。

4 3
3 1 4 1
5 9 2 6
5 3 5 8
9 7 9 3

8
8
8
9

3 1000000000
100 999 999
999 100 999
999 999 100

100000000000
100000000000
100000000000

Hint

样例1解释： 当 $s=1$ 时，路径 $1\to 2\to 3\to 1$ 的总代价为 $1+2+5=8$，并且无法做到总代价不超过 7。
当 $s=4$ 时，路径 $4\to 4\to 4\to 4$ 的总代价为 $3+3+3=9$。