class segtree(): n=1 size=1 log=2 d=[0] op=None e=10**15 def __init__(self,V,OP,E): self.n=len(V) self.op=OP self.e=E self.log=(self.n-1).bit_length() self.size=1<>i) def get(self,p): assert 0<=p and p>=1 r>>=1 return self.op(sml,smr) def all_prod(self): return self.d[1] def max_right(self,l,f): assert 0<=l and l<=self.n assert f(self.e) if l==self.n: return self.n l+=self.size sm=self.e while(1): while(l%2==0): l>>=1 if not(f(self.op(sm,self.d[l]))): while(l1 and (r%2)): r>>=1 if not(f(self.op(self.d[r],sm))): while(r 0: Y[w-c].append(w) i = -1 b = -1 for w in range(W): for j in X[w]: i = max(i,j) if S[h][w] == '#': b = w continue res = seg.prod(max(i,b)+1,w+1) if i > b: res = min(res,w-i) dp[h][w] = res i = W b = W for w in range(W-1,-1,-1): for j in Y[w]: i = min(i,j) if S[h][w] == '#': b = w continue res = seg.prod(w,min(i,b)) if i < b: res = min(res,i - w) dp[h][w] = min(dp[h][w],res) for k in range(W): print(dp[0][k])