The shortest distance

The directed graph is given. Find the shortest distance from the vertex $x$ to other vertices of the graph.

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,...,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