import heapq class DeletableHeapq: def __init__(self, lst=None, reverse=False): if reverse: self.pm = -1 else: self.pm = 1 if lst is None: self.hq = [] else: self.hq = [self.pm * x for x in lst] heapq.heapify(self.hq) self.tot = sum(self.hq) * self.pm self.cnt = {} for x in self.hq: self.cnt[x] = self.cnt.get(x, 0) + 1 self.length = len(self.hq) def __bool__(self): return bool(self.hq) def __len__(self): return self.length @property def sum(self): return self.tot def top(self): if self.hq: return self.hq[0] * self.pm else: return None def __getitem__(self, i): # 先頭要素にアクセスしたいときのみ assert i == 0 return self.top() def push(self, x): self.length += 1 self.cnt[x * self.pm] = self.cnt.get(x * self.pm, 0) + 1 self.tot += x heapq.heappush(self.hq, x * self.pm) def pop(self): if not self.hq: return None self.length -= 1 x = heapq.heappop(self.hq) self.cnt[x] -= 1 self.tot -= x * self.pm self._delete() return x * self.pm def remove(self, x): if self.cnt.get(x * self.pm, 0) == 0: return False self.length -= 1 self.cnt[x * self.pm] -= 1 self.tot -= x self._delete() return True def _delete(self): while self.hq and self.cnt.get(self.hq[0], 0) == 0: heapq.heappop(self.hq) h, w = map(int, input().split()) S = [input() for _ in range(h)] dp = [0] * w for i in range(h - 1, -1, -1): add = [[] for _ in range(w)] rem = [[] for _ in range(w)] L = [0] * w l = 0 for j in range(w): if S[i][j] == "#": l = j + 1 L[j] = l R = [0] * w r = w - 1 for j in range(w - 1, -1, -1): if S[i][j] == "#": r = j - 1 R[j] = r for j in range(w): if S[i][j] == "#": continue l = max(L[j], j - dp[j]) r = min(R[j], j + dp[j]) add[l].append(dp[j]) rem[r].append(dp[j]) hq = DeletableHeapq() hq.push(1 << 30) dp = [1 << 30] * w for j in range(w): for a in add[j]: hq.push(a) dp[j] = hq[0] for a in rem[j]: hq.remove(a) for j in range(1, w): dp[j] = min(dp[j], dp[j - 1] + 1) for j in range(w - 2, -1, -1): dp[j] = min(dp[j], dp[j + 1] + 1) for j in range(w): if S[i][j] == "#": dp[j] = 1 << 30 print(*dp, sep="\n")