#include using namespace std; using ll=long long; #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() template bool chmax(T &a, T b){if (a < b){a = b;return true;} else return false;} template bool chmin(T &a, T b){if (a > b){a = b;return true;} else return false;} template struct segment_tree { using T = typename M::T; public: explicit segment_tree() {} explicit segment_tree(int N) : segment_tree(std::vector(N, M::e())) {} explicit segment_tree(const std::vector& v) { int N = (int)v.size(); n = N; size = 1; while (size < N) size <<= 1; data.resize(2 * size, M::e()); for (int i = 0; i < N; i++) data[size + i] = v[i]; for (int i = size - 1; i >= 1; i--) update(i); }; void set(int p, T x) { assert(0 <= p && p < n); p += size; data[p] = x; while (p > 1) { p >>= 1; update(p); } } T get(int p) { assert(0 <= p && p < n); p += size; return data[p]; } T prod(int l, int r) { assert(0 <= l && l <= r && r <= n); T vl = M::e(), vr = M::e(); l += size; r += size; while (l < r) { if (l & 1) vl = M::op(vl, data[l++]); if (r & 1) vr = M::op(data[--r], vr); l >>= 1; r >>= 1; } return M::op(vl, vr); } T all_prod() { return data[1]; } private: int n, size; std::vector data; void update(int p) { data[p] = M::op(data[2 * p], data[2 * p + 1]); } }; const int INF=1<<30; struct M{ using T=int; static T op(T l,T r){return min(l,r);} static T e(){return INF;} }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int H,W; cin>>H>>W; vectorS(H); for(int i=0;i>S[i]; segment_treeseg(W); for(int j=0;j=0;i--){ for(int j=0;jseg2(W); int l=0,r=0; while(l1){ int mid=(ok+ng)/2; if(seg.prod(max(l,j-mid+1),min(r,j+mid))>=mid)ok=mid; else ng=mid; } seg2.set(j,ok); } l=r; }else{ l++; } } swap(seg,seg2); } for(int j=0;j