//generated by GPT-5.4 modified by hamamu
namespace SlideMinSpace{
using ll=long long;

template<class T,class Compare> struct slideextreme{
    /*
    スライドmin/max用の共通実装。
    Compare は「後ろの要素が、新しく入る要素より劣っているか」を表す比較。
    - 最大値を取りたいとき: less<T>
      例: data < x なら data は今後最大候補になれないので捨てる
    - 最小値を取りたいとき: greater<T>
      例: data > x なら data は今後最小候補になれないので捨てる
    deque の先頭には、常に現在ウィンドウの答えが来る。
    */
    deque<pair<T,int>> dq; //<値, 追加順 index>
    int headIdx=0;         //現在ウィンドウ先頭の index
    int tailIdx=-1;        //現在までに追加した末尾の index
    Compare comp=Compare();

    slideextreme() = default;

    void push_back(const T &x){
        // 後ろにある「今後絶対に答えになれない要素」を捨てる
        while (!dq.empty()){
            const T &data=dq.back().first;
            if (comp(data,x)) dq.pop_back();
            else break;
        }
        dq.emplace_back(x,++tailIdx);
    }

    void pop_front(){
        assert(headIdx<=tailIdx);
        if (!dq.empty() && dq.front().second==headIdx) dq.pop_front();
        headIdx++;
    }

    T get()const{
        assert(!dq.empty());
        return dq.front().first;
    }
};
template<class T> using slidemax = slideextreme<T,less<T>>;
template<class T> using slidemin = slideextreme<T,greater<T>>;

template<class T,class Compare>
vector<T> slideextreme1d(const vector<T> &A,ll w){
    ll N=(ll)A.size();
    assert(1<=w && w<=N);

    vector<T> ret;
    slideextreme<T,Compare> se;

    for (ll l=0,r=w-1; r<N; ++l,++r){
        if (l==0){ // 最初の幅w個で初期ウィンドウを作る
            for (ll i=0; i<w; ++i)
              se.push_back(A[i]);
        }
        else{ // 1つ右へスライド
            se.push_back(A[r]);
            se.pop_front();
        }
        ret.push_back(se.get());
    }
    return ret;
}

template<class T>
vector<T> slidemin1d(const vector<T> &A,ll w){
    return slideextreme1d<T,greater<T>>(A,w);
}
template<class T>
vector<T> slidemax1d(const vector<T> &A,ll w){
    return slideextreme1d<T,less<T>>(A,w);
}

template<class T,class Compare>
vector<vector<T>> slideextreme2d(const vector<vector<T>> &A,ll h,ll w){
    ll H=(ll)A.size();
    ll W=H==0 ? 0 : (ll)A[0].size();
    assert(1<=h && h<=H && 1<=w && w<=W);

    // まず各行に対して幅 w のスライドmin/maxを取る
    vector<vector<T>> rowAns(H);
    for (ll i=0; i<H; ++i)
        rowAns[i]=slideextreme1d<T,Compare>(A[i],w);

    // 次に各列に対して高さ h のスライドmin/maxを取る
    vector<vector<T>> ret(H-h+1,vector<T>(W-w+1));
    for (ll j=0; j<(ll)rowAns[0].size(); ++j){
        vector<T> col;
        for (ll i=0; i<H; ++i)
          col.push_back(rowAns[i][j]);

        vector<T> colAns=slideextreme1d<T,Compare>(col,h);
        assert((ll)colAns.size()==H-h+1);

        for (ll i=0; i<(ll)colAns.size(); ++i)
            ret[i][j]=colAns[i];
    }
    return ret;
}

template<class T>
vector<vector<T>> slidemin2d(const vector<vector<T>> &A,ll h,ll w){
    return slideextreme2d<T,greater<T>>(A,h,w);
}
template<class T>
vector<vector<T>> slidemax2d(const vector<vector<T>> &A,ll h,ll w){
    return slideextreme2d<T,less<T>>(A,h,w);
}
}//SlideMinSpace
using SlideMinSpace::slidemin;
using SlideMinSpace::slidemax;
using SlideMinSpace::slidemin1d;
using SlideMinSpace::slidemax1d;
using SlideMinSpace::slidemin2d;
using SlideMinSpace::slidemax2d;
/*
- ---- スライドmin/max ----
ウィンドウ末尾にデータを追加、先頭からデータを取り出すとし、
ウィンドウ内のmin/maxを答えられるデータ構造。O(N)。

slidemin<ll> sm; //min
slidemax<ll> sm; //max
sm.push_back(x); //ウィンドウ末尾にx追加
sm.pop_front();  //ウィンドウ先頭を削除
ll va=sm.get();  //ウィンドウ内min/maxを取得

- ---- 1D配列の固定幅スライドmin/max ----
vll mns=slidemin1d(A,w); //mns[i]: 左端A[i]、幅w内のmin
vll mxs=slidemax1d(A,w); //mxs[i]:       〃         max

- ---- 2D配列の固定矩形スライドmin/max ----
vvll mnss=slidemin2d(A,h,w); //mnss[i][j]: 左上Aij,サイズh*wの矩形内min
vvll mxss=slidemax2d(A,h,w); //mxss[i][j]:           〃             max
*/