ABC291 F - Teleporter and Closed off

INF = float("inf")
 
n, m = map(int, input().split())
 
graph = [[] for _ in range(n)]
 
edges = set()
 
for i in range(n):
    s = input()
    for j in range(m):
        if s[j] == "1":
            graph[i].append(i + j + 1)
            edges.add((i, i + j + 1))
 
# dp0[i] := v(0) ~ v(i)への最短距離
dp0 = [INF] * n
# dp1[i] := v(i) ~ v(N - 1)への最短距離
dp1 = [INF] * n
 
dp0[0] = 0
for u in range(n):
    for v in graph[u]:
        dp0[v] = min(dp0[v], dp0[u] + 1)
 
dp1[-1] = 0
for u in range(n)[::-1]:
    for v in graph[u]:
        dp1[u] = min(dp1[u], dp1[v] + 1)
 
for k in range(1, n - 1):
    ans = INF
    for via in range(k - m, k):
        for exit in range(k + 1, k + m + 1):
            if (via, exit) in edges:
                ans = min(ans, dp0[via] + dp1[exit] + 1)
    if ans is INF:
        print(-1)
    else:
        print(ans)