//generated by GPT-5.6 Sol modified by hamamu
namespace BITSpace{
using ll  = long long;
using Int = long long;

// デフォルトの加算・減算
template<class T> struct BITAdd{
    T operator()(const T &a,const T &b)const{ return a+b; }
};
template<class T> struct BITSub{
    T operator()(const T &a,const T &b)const{ return a-b; }
};

template<class T,class Ope=BITAdd<T>,class Sub=BITSub<T>>
struct BIT{
    // sub=nullptr_t のとき、逆演算が必要な関数を requires で制限する。
    static constexpr bool HAS_SUB=!is_same_v<Sub,nullptr_t>;

    ll n=0,st=0; // 添字数と公開添字の基準
    T e;        // 集約の単位元
    Ope op;     // 値同士の合成
    Sub sub;    // 累積値から区間値を取り出す逆演算

    // bit[i]は1-origin  公開添字iはbit[i-st+1]側に対応
    vector<T> bit;

    // type_identity_t<T>で型推論対象から外れ、0LLと書く必要がなくなる
    BIT(T,ll n,const type_identity_t<T> &e=T()):n(n),e(e),op(Ope()),sub(Sub()){ init(n); }
    BIT(T,ll n,const type_identity_t<T> &e,Ope op,Sub sub):n(n),e(e),op(move(op)),sub(move(sub)){ init(n); }
    BIT(T,const vector<T> &ini,const type_identity_t<T> &e=T()):n((ll)ini.size()),e(e),op(Ope()),sub(Sub()){ init(ini); }
    BIT(T,const vector<T> &ini,const type_identity_t<T> &e,Ope op,Sub sub):n((ll)ini.size()),e(e),op(move(op)),sub(move(sub)){ init(ini); }

    void setOffset(ll st){ this->st=st; }
    Int St()const{ return (Int)st; }
    Int En()const{ return (Int)(st+n-1); }
    template<class... I> bool in(I... i)const{ return ((st<=i && i<=st+n-1) && ...); }

    // 先頭の1要素は1-origin用のダミー。
    void init(ll n){
        assert(n>=0);
        this->n=n;
        bit.assign(n+1,e);
    }

    void init(const vector<T> &ini){
        init((ll)ini.size());
        //iniを葉として入れ、各要素を一度だけ親へ集約
        for(ll i=0;i<n;++i) bit[i+1]=ini[i];
        for(ll i=1;i<=n;++i){
            ll p=i+(i&-i);
            if(p<=n) bit[p]=op(bit[p],bit[i]);
        }
    }

    void apply(ll i,const T &x){
        assert(in(i));
        // 公開添字を内部添字へ戻し、担当区間を持つ祖先へ合成する。
        i-=st;
        for(ll j=i+1;j<=n;j+=j&-j) bit[j]=op(bit[j],x);
    }

    void set(ll i,const T &x) requires(HAS_SUB){
        assert(in(i));
        apply(i,sub(x,get(i))); //現在値との差分を追加してA[i]=xにする
    }

    T get(ll i)const requires(HAS_SUB){
        if(!in(i)) return e;
        return sub(prefix(i),prefix(i-1)); //1点はiからi-1を引く
    }
    T operator[](ll i)const requires(HAS_SUB){ return get(i); }

    vector<T> toVector()const requires(HAS_SUB){
        vector<T> a;
        for(ll k=0;k<n;++k) a.push_back(get(St()+k));
        return a;
    }

    T get(ll l,ll r)const requires(HAS_SUB){
        if(r<l) return e;
        l=max(l,st),r=min(r,st+n-1);
        return r<l ? e : sub(prefix(r),prefix(l-1));
    }

    T prefix(ll r)const{
        if(r<st || n==0) return e;
        r=min(r,st+n-1)-st;
        T ret=e;
        // 右端から、末尾の担当区間を順に取り除きながら集約する。
        for(ll j=r+1;j>0;j-=j&-j) ret=op(ret,bit[j]);
        return ret;
    }

    T total()const{ return prefix(st+n-1); }

    //---- BIT上二分探索
    pair<Int,T> floorGroup(ll l,T x)const requires(HAS_SUB);
    pair<Int,T> ceilGroup(ll l,T x)const requires(HAS_SUB);
    pair<Int,T> floorGroupRev(ll r,T x)const requires(HAS_SUB);
    pair<Int,T> ceilGroupRev(ll r,T x)const requires(HAS_SUB);

    //---- 多重集合用API
    void insert(ll x) requires(HAS_SUB);
    bool erase(ll x) requires(HAS_SUB);
    bool contains(ll x)const requires(HAS_SUB);
    Int leftnumof(ll x)const requires(HAS_SUB);
    Int rightnumof(ll x)const requires(HAS_SUB);
    Int rank(ll x)const requires(HAS_SUB);
    Int rrank(ll x)const requires(HAS_SUB);
    Int nthsmall(ll r)const requires(HAS_SUB);
    Int nthbig(ll r)const requires(HAS_SUB);

    //---- 動的imos用API
    void rangeadd(ll l,ll r,const T &x) requires(HAS_SUB);
    T imos(ll i)const;

    //---- 01列用API
    Int count(ll b,ll l,ll r)const requires(HAS_SUB);
    Int ceilIdxOf(ll b,ll i,ll d=1)const requires(HAS_SUB);
    Int floorIdxOf(ll b,ll i,ll d=1)const requires(HAS_SUB);
    void flip(ll i) requires(HAS_SUB);
    pair<Int,Int> runRange(ll i)const requires(HAS_SUB);
    bool isAll(ll b,ll l,ll r)const requires(HAS_SUB);
    bool isAny(ll b,ll l,ll r)const requires(HAS_SUB);

private:
    ll select01(ll b,ll k)const;

    // P[p]=op(A[0],...,A[p-1]) とする。
    // 単調な条件 ok(p,P[p]) を満たす最大 p と P[p] を binary lifting で求める。なければp=-1。
    template<class F>
    pair<ll,T> maxPrefix(F ok)const{
        if(!ok(0,e)) return {-1,e};
        ll p=0;
        T cur=e;
        for(ll step=(ll)bit_floor((unsigned long long)n);step;step>>=1){
            ll np=p+step;
            if(np<=n){
                T nxt=op(cur,bit[np]);
                // 条件を保つ区間だけ採用し、次の小さいstepへ進む。
                if(ok(np,nxt)) p=np,cur=move(nxt);
            }
        }
        return {p,cur};
    }

};
}
using BITSpace::BIT;
/*
- ---- 定義 ----
BIT bit(T(),N);        //データ型T、[0,N-1]、初期値0(正確にはT())、演算は加減算
BIT bit(T(),ini);      //第2引数iniならO(N)構築
BIT bit(T(),Nかini,e); //単位元e指定
BIT bit(T(),Nかini,e,op,sub);    //op指定,逆演算sub有
BIT bit(T(),Nかini,e,op,nullptr);//op指定,逆演算sub無  一部操作不可となる

//op=maxの例
BIT bit(ll(),ini,-INF,[](ll a,ll b){return max(a,b);},nullptr);

//op=XORの例
BIT bit(ll(),ini,0,
    [](ll a,ll b){return a^b;},  //op
    [](ll a,ll b){return a^b;}); //sub

- ---- 範囲関連 ----
bit.setOffset(st); //添字の基準を変更 範囲が[st,st+N-1]になる
ll l=bit.St(),r=bit.En(); //現在の範囲[st,st+N-1]。N=0ならEn()==St()-1
bool a=bit.in(i,j,…可変引数); //true:すべて範囲内

- ---- 操作 ----
bit.init(N);   //サイズNでクリア。stは維持
bit.init(ini); //iniで再構築。stは維持
bit.apply(i,x);//A[i]<-op(A[i],x)
bit.set(i,x);  //A[i]<-x  sub有時のみ

- ---- 取得 ---- [St(),En()]外は単位元として扱う
ll x=bit.get(i);   //A[i]  sub有時のみ
ll x=bit[i];       //A[i]  sub有時のみ
ll x=bit.get(l,r); //[l,r] sub有時のみ
ll x=bit.prefix(r);//[St(),r]。r<St()ならe、r>En()なら全体の集約値
T x=bit.total();   //全要素の集約値
vll a=bit.toVector(); //a[k]=A[St()+k]  sub有時のみ
if(bit.n) dumpNd("bit",bit.toVector(),args().sx(bit.St()).labels({"i"})); //dump

以下は使用時別途貼る。
- ---- BIT上二分探索 ---- `bitsearch`
- ---- 多重集合用API ---- `bitmultiset`
- ---- 動的imos用API ---- `bitimos`
- ---- 01列用API ----     `bitbinary`
*/

/***************************/
/****** BIT上二分探索 ******/
/***************************/
namespace BITSpace{
template<class T,class Ope,class Sub>
pair<Int,T> BIT<T,Ope,Sub>::floorGroup(ll l,T x)const requires(HAS_SUB){
    assert(st<=l && l<=st+n);
    //prefix(l-1)+x以下となる最大prefixをBIT上で二分探索する
    T base=prefix(l-1),th=op(base,x);
    auto [p,pref]=maxPrefix([&](ll,const T &v){ return !(th<v); });
    T range=sub(pref,base);
    return {(Int)(st+p-1),sub(x,range)};
}

template<class T,class Ope,class Sub>
pair<Int,T> BIT<T,Ope,Sub>::ceilGroup(ll l,T x)const requires(HAS_SUB){
    assert(st<=l && l<=st+n);
    if(x==e) return {(Int)(l-1),e}; //x=0なら空区間r=l-1が最小の答
    //閾値prefix(l-1)+x未満となる最大prefixを二分探索で得る
    //その次の要素(=p)が初めて閾値以上になる位置
    T base=prefix(l-1),th=op(base,x);
    auto [p,pref]=maxPrefix([&](ll,const T &v){ return v<th; });
    if(p==n) return {(Int)(st+n),e};
    T range=sub(prefix(st+p),base);
    return {(Int)(st+p),sub(range,x)};
}

template<class T,class Ope,class Sub>
pair<Int,T> BIT<T,Ope,Sub>::floorGroupRev(ll r,T x)const requires(HAS_SUB){
    assert(st-1<=r && r<=st+n-1);
    //sum[l,r]=prefix(r)-prefix(l-1)なのでprefix(l-1)>=prefix(r)-xを探す
    T total=prefix(r),th=sub(total,x);
    ll l=st+maxPrefix([&](ll,const T &v){ return v<th; }).first+1;
    T range=sub(total,prefix(l-1));
    return {(Int)l,sub(x,range)};
}

template<class T,class Ope,class Sub>
pair<Int,T> BIT<T,Ope,Sub>::ceilGroupRev(ll r,T x)const requires(HAS_SUB){
    assert(st-1<=r && r<=st+n-1);
    if(x==e) return {(Int)(r+1),e}; //x=0なら、空区間l=r+1が最大の答
    T total=prefix(r);
    //sum[l,r]=prefix(r)-prefix(l-1)なのでprefix(l-1)<=prefix(r)-xを探す
    T th=sub(total,x);
    auto [l,pref]=maxPrefix([&](ll,const T &v){ return !(th<v); });
    T range=sub(total,pref);
    return {(Int)(st+l),sub(range,x)};
}
}
/*
// BIT本体を上に貼り付けること

- ---- BIT上二分探索 ---- op,subが加減算、x>=0、全Ai>=0が前提
auto [r,rem]=bit.floorGroup(l,x);    //Al+A_{l+1}+…+Ar+rem=xなる最大のr
auto [r,rem]=bit. ceilGroup(l,x);    //Al+A_{l+1}+…+Ar=x+remなる最小のr ない時En()+1
auto [l,rem]=bit.floorGroupRev(r,x); //Ar+A_{r-1}+…+Al+rem=xなる最小のl
auto [l,rem]=bit. ceilGroupRev(r,x); //Ar+A_{r-1}+…+Al=x+remなる最大のl ない時St()-1
*/

/***************************/
/****** 多重集合用API ******/
/***************************/
namespace BITSpace{
//---- 多重集合用API: A[x]を値xの個数として扱う
template<class T,class Ope,class Sub>
void BIT<T,Ope,Sub>::insert(ll x) requires(HAS_SUB){ apply(x,T(1)); }

template<class T,class Ope,class Sub>
bool BIT<T,Ope,Sub>::erase(ll x) requires(HAS_SUB){
    // 負の個数にすると累積値の単調性が崩れるため、削除前に確認する。
    if(!contains(x)) return false;
    apply(x,sub(e,T(1)));
    return true;
}

template<class T,class Ope,class Sub>
bool BIT<T,Ope,Sub>::contains(ll x)const requires(HAS_SUB){ return get(x)>e; }

template<class T,class Ope,class Sub>
Int BIT<T,Ope,Sub>::leftnumof(ll x)const requires(HAS_SUB){ return (Int)prefix(x); }

template<class T,class Ope,class Sub>
Int BIT<T,Ope,Sub>::rightnumof(ll x)const requires(HAS_SUB){ return (Int)get(x,st+n-1); }

// 自分より手前に並ぶ個数に1を足す。
template<class T,class Ope,class Sub>
Int BIT<T,Ope,Sub>::rank(ll x)const requires(HAS_SUB){
    return (Int)(prefix(x-1)+1);
}

template<class T,class Ope,class Sub>
Int BIT<T,Ope,Sub>::rrank(ll x)const requires(HAS_SUB){ return (Int)(sub(total(),prefix(x))+1); }

template<class T,class Ope,class Sub>
Int BIT<T,Ope,Sub>::nthsmall(ll r)const requires(HAS_SUB){
    assert(r>=1);
    // 累積個数がr未満の最大prefixの直後が、r個目の位置。
    return (Int)(st+maxPrefix([&](ll,const T &v){ return v<T(r); }).first);
}

template<class T,class Ope,class Sub>
Int BIT<T,Ope,Sub>::nthbig(ll r)const requires(HAS_SUB){
    assert(r>=1);
    T cnt=total();
    // 有効な順位だけを、昇順での順位に変換する。
    if(T(r)>cnt) return (Int)(st-1);
    return nthsmall(sub(cnt,T(r))+1);
}
}
/*
// BIT本体を上に貼り付けること

- ---- 多重集合専用 ---- 加減算・単位元0・全Aiが非負整数の個数前提。すべてO(logN)
// 値xは[St(),En()]。insertは範囲内のみ。範囲外の値の個数は0。
ll nm=bit.total();      //集合の要素数（重複含む）
bit.insert(x);          //集合にxを1つ挿入
bool b=bit.erase(x);    //xを1つ削除。存在しなければ変更せずfalse
bool b=bit.contains(x); //true:x∈集合
ll r=bit.rank(x);  //xの小さい方からの順位 1-origin xがなければ挿入した場合の順位
ll r=bit.rrank(x); //xの大きい方からの順位 1-origin xがなければ挿入した場合の順位
ll nm=bit.leftnumof(x);  //x以下の個数
ll nm=bit.rightnumof(x); //x以上の個数
ll nm=bit[x];            //xの個数
ll x=bit.nthsmall(r); //r番目に小さい要素 1-origin。ない時En()+1
ll x=bit.nthbig(r);   //r番目に大きい要素 1-origin。ない時St()-1
*/

/***************************/
/****** 動的imos用API ******/
/***************************/
namespace BITSpace{
//---- 動的imos用API: A[i]を差分として扱う
template<class T,class Ope,class Sub>
void BIT<T,Ope,Sub>::rangeadd(ll l,ll r,const T &x) requires(HAS_SUB){
    l=max(l,st),r=min(r,st+n-1);
    if(l>r) return;
    // 左端で加算を開始し、右端の次で打ち消す。末尾の外への更新は不要。
    apply(l,x);
    if(r<st+n-1) apply(r+1,sub(e,x));
}

template<class T,class Ope,class Sub>
T BIT<T,Ope,Sub>::imos(ll i)const{ return prefix(i); }

}
/*
// BIT本体を上に貼り付けること

- ---- 動的imos専用 ---- 加減算・単位元0前提。すべてO(logN)
// BITには差分配列を保持。init(ini)にも差分配列を渡す。
bit.rangeadd(l,r,x); //区間[l,r]に+x
T x=bit.imos(i);     //第i要素の値（差分の累積和）
*/

/***************************/
/******** 01列用API ********/
/***************************/
namespace BITSpace{
//---- 01列用API
template<class T,class Ope,class Sub>
Int BIT<T,Ope,Sub>::count(ll b,ll l,ll r)const requires(HAS_SUB){
    assert(b==0 || b==1);
    l=max(l,st),r=min(r,st+n-1);
    if(l>r) return 0;
    ll ones=(ll)get(l,r);
    return (Int)(b ? ones : r-l+1-ones);
}

template<class T,class Ope,class Sub>
Int BIT<T,Ope,Sub>::ceilIdxOf(ll b,ll i,ll d)const requires(HAS_SUB){
    assert(in(i) && d>=1);
    // iより前の個数を足し、列全体での順位に直す。
    if(d>count(b,i,st+n-1)) return (Int)(st+n);
    return (Int)select01(b,(ll)count(b,st,i-1)+d);
}

template<class T,class Ope,class Sub>
Int BIT<T,Ope,Sub>::floorIdxOf(ll b,ll i,ll d)const requires(HAS_SUB){
    assert(in(i) && d>=1);
    // i以下の最後のbから、d-1個だけ左へ戻った順位を探す。
    ll total=count(b,st,i);
    return (Int)(d>total ? st-1 : select01(b,total-d+1));
}

template<class T,class Ope,class Sub>
void BIT<T,Ope,Sub>::flip(ll i) requires(HAS_SUB){
    assert(in(i));
    set(i,1-get(i));
}

template<class T,class Ope,class Sub>
pair<Int,Int> BIT<T,Ope,Sub>::runRange(ll i)const requires(HAS_SUB){
    assert(in(i));
    // 反対の値が現れる位置に挟まれた区間がランになる。
    ll b=1-(ll)get(i);
    return {floorIdxOf(b,i)+1,ceilIdxOf(b,i)-1};
}

// 全要素の一致は、反対の値が存在しないことと同じ。
template<class T,class Ope,class Sub>
bool BIT<T,Ope,Sub>::isAll(ll b,ll l,ll r)const requires(HAS_SUB){ return count(1-b,l,r)==0; }

template<class T,class Ope,class Sub>
bool BIT<T,Ope,Sub>::isAny(ll b,ll l,ll r)const requires(HAS_SUB){ return count(b,l,r)!=0; }

// 左からk個目のbの位置。prefix内の0の個数は長さ-1の個数。
template<class T,class Ope,class Sub>
ll BIT<T,Ope,Sub>::select01(ll b,ll k)const{
    return st+maxPrefix([&](ll p,const T &v){
        return (b ? (ll)v : p-(ll)v)<k;
    }).first;
}
}
using BITSpace::BIT;
/*
// BIT本体を上に貼り付けること

- ---- 01列専用 ---- 加減算・単位元0前提。すべてO(logN)
ll c=bit.count(b,l,r); //区間[l,r]のb(0/1)の個数  区間外は0も1もないとする
ll r=bit. ceilIdxOf(b,i,d=1); //i以降のd個目のb(0/1)の位置 ない時En()+1
ll l=bit.floorIdxOf(b,i,d=1); //i以前のd個目のb(0/1)の位置 ない時St()-1
bit.flip(i);                  //iを反転
auto [l,r]=bit.runRange(i);   //iを含むランの左右端
bool a=bit.isAll(b,l,r);      //区間[l,r]がすべてb(0/1)か
bool a=bit.isAny(b,l,r);      //区間[l,r]にb(0/1)があるか
*/