The shortest distance

Input

The first line contains two integers $n$ and x~(1 \le n \le 1000, 1 \le x \le n) — the number of vertices in a graph and the starting vertex. Each of the next $n$ lines contains $n$ numbers — the adjacency matrix of the graph: the $i$-th line and $j$-th column contains "$1$", if the vertices $i$ and $j$ are connected with the edge, and "$0$", if there is no edge between them. The main diagonal contains zeroes.

Output

Print the numbers d_1, d_2, \ldots, d_n, where d_i is $-1$ if there is no path from $x$ to $i$, or the minimal distance from $x$ to $i$ otherwise.

Examples