Problem Statement

There is a directed graph with $N$ vertices, vertex $1,$ vertex $2,\ldots,$ vertex $N$. For any pair of integers $(i,j)$ with $1 \leq i,j \leq N$, there is exactly one directed edge from vertex $i$ to vertex $j$ with cost $C_{i,j}$.

You are given a positive integer $K$. For each of $s=1,2,\ldots,N$, solve the following problem.

• Among the ways to start at vertex $s$, move along an edge $K$ times, and return to vertex $s$, find the minimum possible total cost of the edges traversed. More formally, find the minimum possible value of $\displaystyle\sum_{i=1}^{K}C_{v_{i-1},v_i}$ for a sequence $v=(v_0,v_1,\ldots,v_K)$ of integers between $1$ and $N$, inclusive, of length $K+1$ satisfying $v_0=v_K=s$.

Constraints

• $1 \le N \le 100$
• $1 \le K \le 10^9$
• $0 \le C_{i,j} \le 10^9\ (1 \le i \le N,1 \le j \le N)$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N K
C_{1,1} C_{1,2} \ldots C_{1,N}
C_{2,1} C_{2,2} \ldots C_{2,N}
\vdots
C_{N,1} C_{N,2} \ldots C_{N,N}

Output

Output $N$ lines. The $i$-th line $(1 \le i \le N)$ should contain the answer to the problem for $s=i$.