#include #include using namespace std; //Disjoint Sparse Table #include #include template struct DST{ int n; vector >dat; DST(const vector&v={}) { n=v.size(); dat.push_back(v); for(int i=2;i(n)); for(int j=i;jn)r=n; r--; if(l==r)return dat[0][l]; int k=31-__builtin_clz(l^r); return min(dat[k][l],dat[k][r]); } }; int H,W; string S[1<<17]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>H>>W; for(int i=0;i>S[i]; vectorprv(W,0); for(int i=H-2;i>=0;i--) { for(int j=0;jnow(W,(int)1e9); DSTdst(prv); for(int j=0;j1) { int mid=(l+r)/2; if(dst.query(j-mid,j+mid+1)<=mid)r=mid; else l=mid; } now[j]=r; } prv=now; } for(int j=0;j