#ifndef MYLOCAL
//# pragma GCC target("avx2")//yukiではNG
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")
#endif
#if defined(NDEBUG)
#undef NDEBUG
#endif
#include "bits/stdc++.h"
using namespace std;
using ll=long long;
using dd=long double;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll,ll>;
using qll=tuple<ll,ll,ll,ll>;
using namespace chrono;
constexpr ll INF = 1201001001001001001;
struct Fast{ Fast(){ cin.tie(0); ios::sync_with_stdio(false); cout<<fixed<<setprecision(numeric_limits<double>::max_digits10); } } fast;
#define EXPAND( x ) x//VS用おまじない
#define overload3(_1,_2,_3,name,...) name
#define overload4(_1,_2,_3,_4,name,...) name
#define overload5(_1,_2,_3,_4,_5,name,...) name
#define rep1(N)          for (ll dmyi = 0; dmyi < (N); dmyi++)
#define rep2(i, N)       for (ll i = 0; i < (N); i++)
#define rep3(i, S, E)    for (ll i = (S); i <= (E); i++)
#define rep4(i, S, E, t) for (ll i = (S); i <= (E); i+=(t))
#define rep(...) EXPAND(overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__))
#define dep3(i, E, S)    for (ll i = (E); i >= (S); i--)
#define dep4(i, E, S, t) for (ll i = (E); i >= (S); i-=(t))
#define dep(...) EXPAND(overload4(__VA_ARGS__, dep4, dep3,_,_)(__VA_ARGS__))
#define ALL1(v)     (v).begin(),     (v).end()
#define ALL2(v,E)   (v).begin(),     (v).begin()+((E)+1)
#define ALL3(v,S,E) (v).begin()+(S), (v).begin()+((E)+1)
#define all(...) EXPAND(overload3(__VA_ARGS__, ALL3, ALL2, ALL1)(__VA_ARGS__))
template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; }return false; }
template<class T> [[nodiscard]] inline T limithi(T a,T b){ return min(a,b); }
template<class T> [[nodiscard]] inline T limitlo(T a,T b){ return max(a,b); }
template<class T> inline bool chlimithi(T &a,T b){ return chmin(a,b); }
template<class T> inline bool chlimitlo(T &a,T b){ return chmax(a,b); }
template<class T> inline auto maxe(T &&v,ll S,ll E){ return *max_element(all(v,S,E)); }
template<class T> inline auto maxe(T &&v){ return *max_element(all(v)); }
template<class T> inline auto mine(T &&v,ll S,ll E){ return *min_element(all(v,S,E)); }
template<class T> inline auto mine(T &&v){ return *min_element(all(v)); }
template<class T,class U=typename remove_reference<T>::type::value_type>
inline U sum(T &&v,ll S,ll E) {return accumulate(all(v,S,E),U());}
template<class T> inline auto sum(T &&v) {return sum(v,0,v.end()-v.begin()-1);}
template<class T> inline ll sz(T &&v){ return (ll)v.size(); }

//cin
struct cinutil{
    template<class T> static void cin1core(T &a){ cin>>a; }
    template<class T,class S> static void cin1core(pair<T,S> &a){
        cin1core(a.first),cin1core(a.second);
    }
    template<class... Args> static void cin1core(tuple<Args...> &a){
        cinTplRec<tuple<Args...>,sizeof...(Args)-1>()(a);
    }
    template<class T,size_t N>
    static void cin1core(array<T,N> &a){ for (int i=0; i<(int)N; ++i) cin>>a[i]; }
private:
    template<class Tpl,int i> struct cinTplRec{
        void operator()(Tpl &a){ cinTplRec<Tpl,i-1>()(a); cin1core(get<i>(a)); }
    };
    template<class Tpl> struct cinTplRec<Tpl,0>{
        void operator()(Tpl &a){ cin1core(get<0>(a)); }
    };
};
template<class T> T cin1(){ T a; cinutil::cin1core(a); return a; }
template<class... Args> tuple<Args...> cins(){ return cin1<tuple<Args...>>(); }

//cout
template<class T,class S> inline ostream &operator<<(ostream &os,const pair<T,S> &a){ return os << a.first << ' ' << a.second; }
template<class T,class S,class R> inline ostream &operator<<(ostream &os,const tuple<T,S,R> &a){ return os << get<0>(a) << ' ' << get<1>(a) << ' ' << get<2>(a); }
template<class T,class S,class R,class Q> inline ostream &operator<<(ostream &os,const tuple<T,S,R,Q> &a){ return os << get<0>(a) << ' ' << get<1>(a) << ' ' << get<2>(a) << ' ' << get<3>(a); }
template<class T> inline ostream &operator<<(ostream &os,const vector<T> &a){ for (ll i=0; i<(ll)a.size(); i++) os<<(i>0?" ":"")<<a[i];  return os; }

inline struct{
  system_clock::time_point st = system_clock::now();
  ll operator()()const{return duration_cast<microseconds>(system_clock::now()-st).count()/1000;}
} timeget;


template<long long MOD> struct mll_{
    using Int = long long;
    using ll = long long;
    ll val_=0;
    /*---- utility ----*/
    mll_ &norm(){ return normR().normS(); }//正規化
    mll_ &normR(){ val_%=MOD; return *this; }//剰余正規化のみ
    mll_ &normS(){ if (val_<0) val_+=MOD; return *this; }//正負正規化のみ
    mll_ &normP(){ if (val_>=MOD) val_-=MOD; return *this; }//加算時正規化
    mll_ &invsg(){ val_=-val_; return normS(); }//正負反転
    ll modinv(int a){//a^-1 mod MOD
        int ypre=0,y=1,apre=MOD;
        while (a>1){
            int t=apre/a;
            apre-=a*t,swap(a,apre);
            ypre-=y*t,swap(y,ypre);
        }
        return y<0 ? y+MOD : y;
    }
    /*---- I/F ----*/
    mll_(){}
    mll_(ll v): val_(v){ norm(); }
    mll_(ll v,bool b): val_(v){} //正規化無のコンストラクタ
    Int val()const{ return (Int)val_; }
    bool isnone() const { return val_==-1; } //true:値なし
    mll_ &none() { val_=-1; return *this; } //値なしにする
    mll_ &inv(){ val_=modinv((int)val_); return *this; }
    mll_ &operator+=(mll_ b){ val_+=b.val_; return normP(); }
    mll_ &operator-=(mll_ b){ val_-=b.val_; return normS(); }
    mll_ &operator*=(mll_ b){ val_*=b.val_; return normR(); }
    mll_ &operator/=(mll_ b){ return *this*=b.inv(); }
    mll_ &operator+=(ll b){ return *this+=mll_(b); }
    mll_ &operator-=(ll b){ return *this-=mll_(b); }
    mll_ &operator*=(ll b){ return *this*=mll_(b); }
    mll_ &operator/=(ll b){ return *this/=mll_(b); }
    mll_ operator-()const{ return mll_(*this).invsg(); }
    mll_ operator+(mll_ b)const{ return mll_(*this)+=b; }
    mll_ operator-(mll_ b)const{ return mll_(*this)-=b; }
    mll_ operator*(mll_ b)const{ return mll_(*this)*=b; }
    mll_ operator/(mll_ b)const{ return mll_(*this)/=b; }
    mll_ operator+(ll b)const{ return mll_(*this)+=b; }
    mll_ operator-(ll b)const{ return mll_(*this)-=b; }
    mll_ operator*(ll b)const{ return mll_(*this)*=b; }
    mll_ operator/(ll b)const{ return mll_(*this)/=b; }
    friend mll_ operator+(ll a,mll_ b){ return b+a; }
    friend mll_ operator-(ll a,mll_ b){ return -b+a; }
    friend mll_ operator*(ll a,mll_ b){ return b*a; }
    friend mll_ operator/(ll a,mll_ b){ return mll_(a)/b; }
    bool operator==(mll_ b)const{ return val_==b.val_; }
    bool operator!=(mll_ b)const{ return val_!=b.val_; }
    bool operator==(ll b)const{ return *this==mll_(b); }
    bool operator!=(ll b)const{ return *this!=mll_(b); }
    friend bool operator==(ll a,mll_ b){ return mll_(a)==b; }
    friend bool operator!=(ll a,mll_ b){ return mll_(a)!=b; }
    friend ostream &operator<<(ostream &os,mll_  a){ return os << a.val_; }
    friend istream &operator>>(istream &is,mll_ &a){ return is >> a.val_; }
    mll_ pow(ll k)const{
        mll_ ret(1,false),a(*this);
        for (; k>0; k>>=1,a*=a) if (k&1)ret*=a;
        return ret;
    }
    static constexpr int mod() { return MOD; }
    //enum{ modll=MOD };
};


template<class T> struct Vector: vector<T>{
  using Int = long long;
  using vT=vector<T>;
  using cvT=const vector<T>;
  using cT=const T;
  using vT::vT; //親クラスのコンストラクタの隠蔽を回避
  using vT::begin,vT::end,vT::insert,vT::erase;
  auto it(Int i){ return begin()+i; }
  auto it(Int i)const{ return begin()+i; }
  Vector(cvT& b):vT(b){}
  Vector(vT&& b):vT(move(b)){}
  Vector(int n,cT& x):vT(n,x){}// ┬ 型推論のためラッパー
  Vector(long long n,cT& x):vT(n,x){}
  template<class S> Vector(const Vector<S>& b):vT(b.begin(),b.end()){}
  template<class S> Vector(const vector<S>& b):vT(b.begin(),b.end()){}
  Vector(Int n,T s,T d){ iota(n,s,d); }
  Vector(Int n,function<T(Int)> g):vT(n){ for(Int i=0;i<n;++i) (*this)[i]=g(i); }
  Vector &operator+=(cvT &b){ assert(size()==b.size()); for(Int i=0;i<size();++i) (*this)[i]+=b[i]; return *this; }
  Vector &operator-=(cvT &b){ assert(size()==b.size()); for(Int i=0;i<size();++i) (*this)[i]-=b[i]; return *this; }
  Vector &operator*=(cvT &b){ assert(size()==b.size()); for(Int i=0;i<size();++i) (*this)[i]*=b[i]; return *this; }
  Vector &operator/=(cvT &b){ assert(size()==b.size()); for(Int i=0;i<size();++i) (*this)[i]/=b[i]; return *this; }
  Vector &operator%=(cvT &b){ assert(size()==b.size()); for(Int i=0;i<size();++i) (*this)[i]%=b[i]; return *this; }
  Vector &operator+=(const Vector<T> &b){ return *this+=(cvT&)b; }
  Vector &operator-=(const Vector<T> &b){ return *this-=(cvT&)b; }
  Vector &operator*=(const Vector<T> &b){ return *this*=(cvT&)b; }
  Vector &operator/=(const Vector<T> &b){ return *this/=(cvT&)b; }
  Vector &operator%=(const Vector<T> &b){ return *this%=(cvT&)b; }
  Vector operator+(cvT &b){ return Vector(*this)+=b; }
  Vector operator-(cvT &b){ return Vector(*this)-=b; }
  Vector operator*(cvT &b){ return Vector(*this)*=b; }
  Vector operator/(cvT &b){ return Vector(*this)/=b; }
  Vector operator%(cvT &b){ return Vector(*this)%=b; }
  Vector operator+(const Vector<T> &b){ return Vector(*this)+=b; }
  Vector operator-(const Vector<T> &b){ return Vector(*this)-=b; }
  Vector operator*(const Vector<T> &b){ return Vector(*this)*=b; }
  Vector operator/(const Vector<T> &b){ return Vector(*this)/=b; }
  Vector operator%(const Vector<T> &b){ return Vector(*this)%=b; }
  template<class S> Vector &operator+=(S x){ for(T &e: *this) e+=x;  return *this; }
  template<class S> Vector &operator-=(S x){ for(T &e: *this) e-=x;  return *this; }
  template<class S> Vector &operator*=(S x){ for(T &e: *this) e*=x;  return *this; }
  template<class S> Vector &operator/=(S x){ for(T &e: *this) e/=x;  return *this; }
  template<class S> Vector &operator%=(S x){ for(T &e: *this) e%=x;  return *this; }
  template<class S> Vector operator+(S x)const{ return Vector(*this)+=x; }
  template<class S> Vector operator-(S x)const{ return Vector(*this)-=x; }
  template<class S> Vector operator*(S x)const{ return Vector(*this)*=x; }
  template<class S> Vector operator/(S x)const{ return Vector(*this)/=x; }
  template<class S> Vector operator%(S x)const{ return Vector(*this)%=x; }
  Vector &operator--(int){ return *this-=1; }
  Vector &operator++(int){ return *this+=1; }
  Vector operator-()const{ return Vector(*this)*=-1; }
  template<class S> friend Vector operator-(S x,const Vector &a){ return -a+=x; }
  T& at(Int i){ assert(i>=0); if(n()<=i)vT::resize(i+1); return vT::operator[](i); }
  Vector slice(Int l,Int r,Int d=1)const{
    Vector ret;
    for(Int i=l;(d>0&&i<=r)||(d<0&&r<=i);i+=d) ret.push_back((*this)[i]);
    return ret;
  }
  Int size()const{ return (Int)vT::size(); }
  Int n()const{ return size(); }
  Vector &push_back(cT& x,Int n=1){ for(Int i=0;i<n;++i){ vT::push_back(x); } return *this; }
  Vector &pop_back(Int n=1){ for(Int i=0;i<n;++i){ vT::pop_back(); } return *this; }
  Vector &push_front(cT& x,Int n=1){ this->insert(0,x,n); return *this; }
  Vector &pop_front(Int n=1){ erase(0,n-1); return *this; }
  T pull_back(){ T x=move(vT::back()); vT::pop_back(); return x; }
  T pull_front(){ T x=move(vT::front()); erase(0); return x; }
  Vector &insert(Int i,cT& x,Int n=1){ insert(it(i),n,x); return *this; }
  Vector &insert(Int i,cvT& b){ insert(it(i),b.begin(),b.end()); return *this; }
  Vector &erase(Int i){ erase(it(i)); return *this; }
  Vector &erase(Int l,Int r){ erase(it(l),it(r+1)); return *this; }
  Vector &erase(const Vector<Int> &idxs){
      for (Int I=0; I<idxs.n(); ++I){
          Int l=idxs[I]+1, r = (I<idxs.n()-1) ? idxs[I+1] : this->n();
          copy(it(l),it(r),it(l-I-1));//[l,r)を前にI+1個ずらす
      }
      vT::resize(this->n()-idxs.n());
      return *this;
  }
  Vector &eraseall(cT& x){ return eraseall(0,size()-1,x); }
  Vector &eraseall(Int l,Int r,cT& x){ erase(remove(it(l),it(r+1),x),it(r+1)); return *this; }
  template<class Pr> Vector &eraseif(Pr pr){ return eraseif(0,size()-1,pr); }
  template<class Pr> Vector &eraseif(Int l,Int r,Pr pr){ erase(remove_if(it(l),it(r+1),pr),it(r+1)); return *this; }
  Vector &concat(cvT &b,Int n=1){
    cvT B = (&b==this) ? *this : vT{};
    for(int i=0;i<n;++i) this->insert(size(),(&b==this)?B:b);
    return *this;
  }
  Vector repeat(Int n){ return Vector{}.concat(*this,n); }
  Vector &reverse(Int l=0,Int r=-1){ r+=r<0?size():0; std::reverse(it(l),it(r+1)); return *this; }
  Vector &rotate(Int m){ return rotate(0,size()-1,m); }
  Vector &rotate(Int l,Int r,Int m){ std::rotate(it(l),it(m),it(r+1)); return *this; }
  Vector &sort(Int l=0,Int r=-1){ r+=r<0?size():0; std::sort(it(l),it(r+1)); return *this; }
  Vector &rsort(Int l=0,Int r=-1){ return sort(l,r).reverse(l,r); }
  template<class Pr> Vector &sort(Pr pr){ return sort(0,size()-1,pr); }
  template<class Pr> Vector &sort(Int l,Int r,Pr pr){ std::sort(it(l),it(r+1),pr); return *this; }
  template<int key> Vector &sortbykey(Int l=0,Int r=-1){
    r+=r<0?size():0;
    sort(l,r,[](cT &x,cT &y){return get<key>(x)<get<key>(y);});
    return *this;
  }
  Vector &uniq(){ erase(unique(begin(),end()),end()); return *this; }
  Vector &sortq(){ return sort().uniq(); }
  Vector &fill(cT& x){ return fill(0,size()-1,x); }
  Vector &fill(Int l,Int r,cT& x){ std::fill(it(l),it(r+1),x); return *this; }
  Vector &copy(Int i,cvT &b,Int n=1){//A[i]スタートでbをn回分コピー
      for (int t=0; t<n; ++t) for (int j=0; j<(int)b.size(); ++j){
          if (i>=size()) return *this;
          if (i>=0) (*this)[i]=b[j];
          i++;
      }
      return *this;
  }
  template<class S=Int> Vector &iota(Int n,T s=0,S d=1){
    vT::resize(n);
    if(n==0) return *this;
    (*this)[0]=s;
    for(int i=1;i<n;++i) (*this)[i]=(*this)[i-1]+d;
    return *this;
  }
  Int count(cT& x)const{ return count(0,size()-1,x); }
  Int count(Int l,Int r,cT& x)const{ return Int(std::count(it(l),it(r+1),x)); }
  template<class Pr> Int countif(Pr pr)const{ return countif(0,size()-1,pr); }
  template<class Pr> Int countif(Int l,Int r,Pr pr)const{ return Int(count_if(it(l),it(r+1),pr)); }
  Int find(cT& x)const{ return find(0,size()-1,x); }
  Int find(Int l,Int r,cT& x)const{ return Int(std::find(it(l),it(r+1),x)-begin()); }
  Int rfind(cT& x)const{ return rfind(0,size()-1,x); }
  Int rfind(Int l,Int r,cT& x)const{
      for (int i=r;i>=l;--i) if ((*this)[i]==x) return i;
      return l-1;
  }
  template<class Pr> Int findif(Pr pr)const{ return findif(0,size()-1,pr); }
  template<class Pr> Int findif(Int l,Int r,Pr pr)const{ return Int(find_if(it(l),it(r+1),pr)-begin()); }
  Vector<Int> findall(cT& x)const{ return findall(0,size()-1,x); }
  Vector<Int> findall(Int l,Int r,cT& x)const{ return findallif(l,r,[&](cT& y){return y==x;}); }
  template<class Pr> Vector<Int> findallif(Pr pr)const{ return findallif(0,size()-1,pr); }
  template<class Pr> Vector<Int> findallif(Int l,Int r,Pr pr)const{
    Vector<Int> ret;
    for(Int i=l;i<=r;++i) if(pr((*this)[i])) ret.push_back(i);
    return ret;
  }
  Int  flooridx(cT& x)const{ return Int(upper_bound(begin(),end(),x)-begin()-1); }
  Int   ceilidx(cT& x)const{ return Int(lower_bound(begin(),end(),x)-begin()); }
  Int  leftnmof(cT& x)const{ return flooridx(x)+1; }
  Int rightnmof(cT& x)const{ return size()-ceilidx(x); }
  bool contains(cT& x)const{ Int i=flooridx(x); return i>=0 && (*this)[i]==x; }
  template<class Pr> Int  flooridx(cT& x,Pr pr)const{ return Int(upper_bound(begin(),end(),x,pr)-begin()-1); }
  template<class Pr> Int   ceilidx(cT& x,Pr pr)const{ return Int(lower_bound(begin(),end(),x,pr)-begin()); }
  template<class Pr> Int  leftnmof(cT& x,Pr pr)const{ return flooridx(x,pr)+1; }
  template<class Pr> Int rightnmof(cT& x,Pr pr)const{ return size()-ceilidx(x,pr); }
  template<class Pr> bool contains(cT& x,Pr pr)const{ Int i=flooridx(x,pr); return i>=0 && (*this)[i]==x; }

  template<class S> using VV    = Vector<Vector<S>>; template<class S> using sVV    = vector<vector<S>>;
  template<class S> using VVV   = Vector<VV<S>>;     template<class S> using sVVV   = vector<sVV<S>>;
  template<class S> using VVVV  = Vector<VVV<S>>;    template<class S> using sVVVV  = vector<sVVV<S>>;
  template<class S> using VVVVV = Vector<VVVV<S>>;   template<class S> using sVVVVV = vector<sVVVV<S>>;
  auto tostd()const{ return tov(*this); }
  template <class S> static vector<S> tov(const Vector<S>&v){ return v; }
  template <class S> static sVV<S>    tov(const VV<S>    &v){ sVV<S>    ret; for(auto&& e:v) ret.push_back(e);         return ret; }
  template <class S> static sVVV<S>   tov(const VVV<S>   &v){ sVVV<S>   ret; for(auto&& e:v) ret.push_back(e.tostd()); return ret; }
  template <class S> static sVVVV<S>  tov(const VVVV<S>  &v){ sVVVV<S>  ret; for(auto&& e:v) ret.push_back(e.tostd()); return ret; }
  template <class S> static sVVVVV<S> tov(const VVVVV<S> &v){ sVVVVV<S> ret; for(auto&& e:v) ret.push_back(e.tostd()); return ret; }
};


#if 0
#define MODLL (1000000007LL)
#else
#define MODLL (998244353LL)
#endif
using mll = mll_<MODLL>;
//using mll = fraction;



namespace SolvingSpace{

template<class T> using vector = Vector<T>;
using    vll=vector<   ll>; using    vmll=vector<   mll>; using    vdd=vector<   dd>;
using   vvll=vector<  vll>; using   vvmll=vector<  vmll>; using   vvdd=vector<  vdd>;
using  vvvll=vector< vvll>; using  vvvmll=vector< vvmll>; using  vvvdd=vector< vvdd>;
using vvvvll=vector<vvvll>; using vvvvmll=vector<vvvmll>; using vvvvdd=vector<vvvdd>;
using   vpll=vector<  pll>; using    vtll=vector<   tll>; using   vqll=vector<  qll>;
using  vvpll=vector< vpll>; using   vvtll=vector<  vtll>; using  vvqll=vector< vqll>;
using vss=vector<string>;
template<class T> vector<T> cinv(ll nm){ return vector<T>(nm,[](ll i){ (void)i; return cin1<T>(); }); }
template<class T> vector<vector<T>> cinvv(ll H,ll W){ return vector<vector<T>>(H,[&](ll i){ (void)i; return cinv<T>(W); }); }

/*■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■*/




//generated by GPT-5.4, modified by hamamu
template<class T,class F,class Ope,class Mapping,class Composition>
struct lazyDynamicSegTree{
    using Int = long long;
    using ll = long long;
    using cT = const T;
    using cF = const F;

    Ope ope;                    // データ同士の合成
    Mapping rawMapping;         // 生の作用: mapping(f,x,l,r)  区間は閉区間 [l,r]
    Composition rawComposition; // 生の作用素合成: composition(g,f) は f の後に g
    T e;                        // データの単位元
    F id;                       // 作用素の単位元

    ll B;                     // 添字範囲は [0, 2^B-1]  根/葉の深さがB/0
    int rootid=-1;
    ll offset,offsetOrg;
    ll xr=0;                  // 全添字に仮想的に xor する値

    struct Node{
        T x;                  // 部分木の集約値。自ノードの laz は反映済み
        F laz;                // 子孫へ未伝播の作用。葉では常に id
        array<int,2> cids={-1,-1};

        Node(cT &e,cF &id):x(e),laz(id){}
        ll nChild()const{ return 2-(cids[0]==-1)-(cids[1]==-1); }
    };
    vector<Node> pool;

    lazyDynamicSegTree(
        T,F,Int B,T e,F id,Ope ope,Mapping mapping,Composition composition,Int offset=0
    ):ope(ope),rawMapping(mapping),rawComposition(composition),
        e(e),id(id),B(B),offset(offset),offsetOrg(offset)
    {
        assert(B>=1);
        rootid=newNode();
    }

    void clear(){
        pool.clear();
        rootid=newNode();
        offset=offsetOrg;
        xr=0;
    }

    ll imin()const{ return offset; }
    ll imax()const{ return (1LL<<B)-1+offset; }

    // 見かけ上の全添字に xor を掛ける。
    // 木の形は変えず、以後の探索順・区間解釈だけを変える。
    // offset 付きモードとは併用しない前提。
    void xorAllIndex(ll x){
        assert(offset==0);
        assert(0<=x && x<(1LL<<B));
        xr^=x;
    }

    // 位置 i の葉を削除する。
    // 削除後に空部分木になったノードは、親からの参照も切っていく。
    void erase(ll i){
        if (!IsIn(i)) return;
        ll j=toInner(i);
        ll s=toStored(j);
        Erase(rootid,s,0,(1LL<<B)-1,B);
    }

    // 位置 i に「葉が存在するか」を返す。
    // 値が e かどうかではなく、葉ノードが生成されているかで判定する。
    bool contains(ll i)const{
        if (!IsIn(i)) return false;
        ll j=toInner(i);
        ll s=toStored(j);
        return Exists(rootid,s,0,(1LL<<B)-1,B);
    }

    // i 以下で最大の生成済み位置とその値を返す。なければ {imin()-1, e}。
    pair<ll,T> floor(ll i)const{
        auto [pos,val]=FloorLeaf(normalizeR(i),rootid,0,(1LL<<B)-1,B,id);
        return pos==-1 ? pair<ll,T>{imin()-1,e} : pair<ll,T>{pos+offset,val};
    }

    // i 以上で最小の生成済み位置とその値を返す。なければ {imax()+1, e}。
    pair<ll,T> ceil(ll i)const{
        auto [pos,val]=CeilLeaf(normalizeL(i),rootid,0,(1LL<<B)-1,B,id);
        return pos==(1LL<<B) ? pair<ll,T>{imax()+1,e} : pair<ll,T>{pos+offset,val};
    }

    // 最小の生成済み位置とその値を返す。空なら {imax()+1, e}。
    pair<ll,T> front()const{
        auto [pos,val]=FirstLeaf(rootid,0,(1LL<<B)-1,B,id);
        return pos==(1LL<<B) ? pair<ll,T>{imax()+1,e} : pair<ll,T>{pos+offset,val};
    }

    // 最大の生成済み位置とその値を返す。空なら {imin()-1, e}。
    pair<ll,T> back()const{
        auto [pos,val]=LastLeaf(rootid,0,(1LL<<B)-1,B,id);
        return pos==-1 ? pair<ll,T>{imin()-1,e} : pair<ll,T>{pos+offset,val};
    }

    // 点代入。存在しない点なら新規作成する。
    void set(ll i,cT &x){
        assert(IsIn(i));
        ll j=toInner(i);
        ll s=toStored(j);
        Set(rootid,s,0,(1LL<<B)-1,B,x);
    }

    // 点作用。葉が存在しないなら何もしない。
    void apply(ll i,cF &f){
        apply(i,i,f);
    }

    // 閉区間 [l,r] の「既存の葉」にだけ作用する。
    void apply(ll l,ll r,cF &f){
        l=normalizeL(l);
        r=normalizeR(r);
        if (r<l) return;
        ApplyRange(rootid,l,r,0,(1LL<<B)-1,B,f);
    }

    T operator[](ll i)const{ return prod(i,i); }
    T get(ll i)const{ return prod(i,i); }
    T get(ll l,ll r)const{ return prod(l,r); }

    // 閉区間 [l,r] の集約
    T prod(ll l,ll r)const{
        l=normalizeL(l);
        r=normalizeR(r);
        if (r<l) return e;
        return Prod(l,r,rootid,0,(1LL<<B)-1,B,id);
    }

    T allprod()const{
        return node(rootid).x;
    }

    // [l,p] が初めて true になる最左の p。なければ R+1
    template<class IsOK> ll minRight(ll l,ll R,IsOK isOK)const{
        assert(!isOK(e));
        ll nl=normalizeL(l);
        ll nR=normalizeR(R);
        if (nR<nl) return R+1;
        auto [pos,ignore]=SearchR(nl,rootid,0,(1LL<<B)-1,B,e,id,isOK,false);
        return nR<pos ? R+1 : pos+offset;
    }

    // [l,p] が true を保つ最右の p。なければ l-1
    template<class IsOK> ll maxRight(ll l,ll R,IsOK isOK)const{
        ll pos=minRight(l,R,[&](const T &prd){ return !isOK(prd); });
        return max(pos-1,l-1);
    }

    // [p,r] が初めて true になる最右の p。なければ L-1
    template<class IsOK> ll maxLeft(ll L,ll r,IsOK isOK)const{
        assert(!isOK(e));
        ll nL=normalizeL(L);
        ll nr=normalizeR(r);
        if (nr<nL) return L-1;
        auto [pos,ignore]=SearchL(nr,rootid,0,(1LL<<B)-1,B,e,id,isOK,false);
        return pos<nL ? L-1 : pos+offset;
    }

    // [p,r] が true を保つ最左の p。なければ r+1
    template<class IsOK> ll minLeft(ll L,ll r,IsOK isOK)const{
        ll pos=maxLeft(L,r,[&](const T &prd){ return !isOK(prd); });
        return min(pos+1,r+1);
    }

    // 生成済み葉だけ列挙する。
    // 祖先の lazy は carry に積んで読み、木自体は書き換えない。
    // 列挙順は格納座標順ではなく、xor 後の「見かけ上の添字昇順」。
    vector<pair<ll,T>> enumerate()const{
        vector<pair<ll,T>> ret;
        auto dfs=[&](auto dfs,int v,ll sl,ll sr,ll d,F carry)->void{
            if (v==-1) return;

            const Node &nd=node(v);
            if (d==0){
                // 葉に着いたら、祖先からの carry を反映した見かけ上の値を返す。
                ll i=storedBlockL(sl,d)+offset;
                ret.emplace_back(i,mapping(carry,nd.x,i,i));
                return;
            }

            // 子へ降りるときは、自ノードの laz を carry に積む。
            F nextCarry=composition(carry,nd.laz);

            // low/high は「見かけ上の昇順」で並んでいる。
            auto ch=orderedChildren(v,sl,sr,d);

            if (ch.low.cid !=-1) dfs(dfs,ch.low.cid,ch.low.sl,ch.low.sr,d-1,nextCarry);
            if (ch.high.cid!=-1) dfs(dfs,ch.high.cid,ch.high.sl,ch.high.sr,d-1,nextCarry);
        };
        dfs(dfs,rootid,0,(1LL<<B)-1,B,id);
        return ret;
    }

    vector<T> tov()const{
        vector<T> ret(1LL<<B,e);
        for (auto&& [i,x]:enumerate()) ret[i-offset]=x;
        return ret;
    }

private:
    int newNode(){
        pool.emplace_back(e,id);
        return (int)pool.size()-1;
    }

    Node &node(int v){ return pool[v]; }
    const Node &node(int v)const{ return pool[v]; }

    bool IsIn(ll i)const{ return imin()<=i && i<=imax(); }
    bool IsId(cF &f)const{ return f==id; }

    T mapping(cF &f,cT &x,ll l,ll r)const{
        if (IsId(f)) return x;
        return rawMapping(f,x,l,r);
    }

    F composition(cF &g,cF &f)const{ //f の後に g
        if (IsId(g)) return f;
        if (IsId(f)) return g;
        return rawComposition(g,f);
    }

    ll normalizeL(ll l)const{ return clamp(l-offset,0LL,(1LL<<B)); }
    ll normalizeR(ll r)const{ return clamp(r-offset,-1LL,(1LL<<B)-1); }

    // 公開添字 -> offset を外した内部添字
    ll toInner(ll i)const{ return i-offset; }

    // 内部添字 -> 実際に木へ格納する座標
    // xorAllIndex は木の組み替えではなく、この対応だけを変える。
    ll toStored(ll i)const{ return i^xr; }

    // 深さ d のノード [sl,sr] が表す「見かけ上の連続区間」の左端。
    // 下位 d bit はブロック内で自由に動くため、xor の影響は上位側だけで決まる。
    ll storedBlockL(ll sl,ll d)const{
        return ((sl>>d)^(xr>>d))<<d;
    }

    // 深さ d のノード [sl,sr] が表す「見かけ上の連続区間」の右端。
    ll storedBlockR(ll sl,ll d)const{
        return storedBlockL(sl,d)+((1LL<<d)-1);
    }

    // 深さ d において、見かけ上の昇順で low / high どちらの子が先に来るかを返す。
    // xr の第 d-1 bit が 0 なら 0 側→1 側、1 なら 1 側→0 側になる。
    int childOrderBit(ll d,bool takeHigh)const{
        int lowBit=((xr>>(d-1))&1) ? 1 : 0;
        return takeHigh ? (lowBit^1) : lowBit;
    }

    struct ChildInfo{
        int cid;
        ll sl,sr; // 格納座標上の区間
    };

    struct OrderedChildren{
        ChildInfo low;  // 見かけ上の昇順で先に来る子
        ChildInfo high; // 見かけ上の昇順で後に来る子
    };

    // ノード v の 2 子を、xor 後の見かけ上の昇順に並べて返す
    OrderedChildren orderedChildren(int v,ll sl,ll sr,ll d)const{
        assert(d>=1);
        ll sm=(sl+sr)>>1;
        int lowBit=childOrderBit(d,false);
        int highBit=lowBit^1;

        OrderedChildren ret;
        ret.low={
            node(v).cids[lowBit],
            lowBit==0 ? sl : sm+1,
            lowBit==0 ? sm : sr
        };
        ret.high={
            node(v).cids[highBit],
            highBit==0 ? sl : sm+1,
            highBit==0 ? sm : sr
        };
        return ret;
    }

    // ノード v 全体へ作用 f を掛ける。sl,sr は格納座標上の区間。
    // ここでは subtree 全体が一様に更新されるので、x をまとめて更新し、
    // 子孫への遅延は laz に積むだけでよい。
    void AllApply(int v,cF &f,ll sl,ll sr,ll d){
        Node &nd=node(v);
        ll l=storedBlockL(sl,d)+offset;
        ll r=storedBlockR(sl,d)+offset;
        nd.x = mapping(f,nd.x,l,r);
        if (d==0) nd.laz=id;
        else     nd.laz=composition(f,nd.laz);
    }

    // v の未伝播 lazy を「既存の子にだけ」配る。
    // sparse 実装なので、更新のために新しい子は作らない。
    void Push(int v,ll sl,ll sr,ll d){
        Node &nd=node(v);
        if (d==0 || IsId(nd.laz)) return;

        ll sm=(sl+sr)>>1;
        if (nd.cids[0]!=-1) AllApply(nd.cids[0],nd.laz,sl,sm,d-1);
        if (nd.cids[1]!=-1) AllApply(nd.cids[1],nd.laz,sm+1,sr,d-1);

        nd.laz=id;
    }

    // cids[bit] が未生成なら新規ノードを作る。点代入で新しい葉を生やすときだけ使う。
    int EnsureChild(int v,int bit){
        int cid=node(v).cids[bit];
        if (cid==-1){
            cid=newNode();
            node(v).cids[bit]=cid;
        }
        return cid;
    }

    // 子の x から親の x を再計算する。
    // xr!=0 のときも x 自体は格納座標順で持つため、
    // xor 利用時は ope が順序入れ替えに耐えることが前提。
    void Pull(int v){
        Node &nd=node(v);
        T lx = nd.cids[0]==-1 ? e : node(nd.cids[0]).x;
        T rx = nd.cids[1]==-1 ? e : node(nd.cids[1]).x;
        nd.x = ope(lx,rx);
    }

    // 格納座標 s の葉を x にする。
    // 書き込み系なので、途中で必要な lazy は Push してから降りる。
    void Set(int v,ll s,ll sl,ll sr,ll d,cT &x){
        if (d==0){
            Node &nd=node(v);
            nd.x=x;
            nd.laz=id;  // 葉の laz は常に id
            return;
        }

        Push(v,sl,sr,d);

        ll sm=(sl+sr)>>1;
        if (s<=sm){
            int cid=EnsureChild(v,0);
            Set(cid,s,sl,sm,d-1,x);
        }
        else{
            int cid=EnsureChild(v,1);
            Set(cid,s,sm+1,sr,d-1,x);
        }

        Pull(v);
    }

    // 位置 s の葉が存在するかだけを調べる。
    // 値が e かどうかではなく、葉ノードがあるかで判定する。
    bool Exists(int v,ll s,ll sl,ll sr,ll d)const{
        if (v==-1) return false;
        if (d==0) return true;

        ll sm=(sl+sr)>>1;
        if (s<=sm) return Exists(node(v).cids[0],s,sl,sm,d-1);
        else      return Exists(node(v).cids[1],s,sm+1,sr,d-1);
    }

    // 位置 s の葉を削除し、空になった部分木は親からも切り離す。
    // 戻り値:
    // true  -> この部分木全体が空になった
    // false -> まだこの部分木内に葉が残っている
    bool Erase(int v,ll s,ll sl,ll sr,ll d){
        if (v==-1) return true;

        if (d==0){
            // 葉を削除。pool 上のノード自体は残すが、親から切れば外からは到達しない。
            Node &nd=node(v);
            nd.x=e;
            nd.laz=id;
            return true;
        }

        // 子の状態を正しく保つため、潜る前に未伝播 lazy を既存の子へ配る。
        Push(v,sl,sr,d);

        ll sm=(sl+sr)>>1;
        int bit=(s<=sm ? 0 : 1);
        int cid=node(v).cids[bit];

        // そもそもその子がなければ、消すものはない。
        if (cid==-1) return node(v).nChild()==0;

        bool childEmpty;
        if (bit==0) childEmpty=Erase(cid,s,sl,sm,d-1);
        else       childEmpty=Erase(cid,s,sm+1,sr,d-1);

        // 子部分木が空になったら、親から参照を切る。
        if (childEmpty) node(v).cids[bit]=-1;

        if (node(v).nChild()==0){
            // 自分も空部分木になった。
            Node &nd=node(v);
            nd.x=e;
            nd.laz=id;
            return true;
        }

        // まだ葉が残るなら、子から親の x を再構築する。
        Pull(v);
        return false;
    }

    // 部分木 v の中で、見かけ上もっとも左にある生成済み葉を返す。
    // 返り値の位置は内部添字系 [0, 2^B-1] で、見つからなければ {2^B, e}。
    pair<ll,T> FirstLeaf(int v,ll sl,ll sr,ll d,F carry)const{
        if (v==-1) return {1LL<<B,e};

        const Node &nd=node(v);
        if (d==0){
            ll i=storedBlockL(sl,d);
            return {i,mapping(carry,nd.x,i+offset,i+offset)};
        }
        // 自ノードの lazy を carry に積んでから、見かけ上左の子を優先して降りる。
        carry=composition(carry,nd.laz);
        auto ch=orderedChildren(v,sl,sr,d);

        // 見かけ上左の子を優先し、見つからなければ右の子へ進む。
        auto ret=FirstLeaf(ch.low.cid,ch.low.sl,ch.low.sr,d-1,carry);
        if (ret.first!=(1LL<<B)) return ret;
        return FirstLeaf(ch.high.cid,ch.high.sl,ch.high.sr,d-1,carry);
    }

    // 部分木 v の中で、見かけ上もっとも右にある生成済み葉を返す。
    // 返り値の位置は内部添字系 [0, 2^B-1] で、見つからなければ {-1, e}。
    pair<ll,T> LastLeaf(int v,ll sl,ll sr,ll d,F carry)const{
        if (v==-1) return {-1,e};

        const Node &nd=node(v);
        if (d==0){
            ll i=storedBlockL(sl,d);
            return {i,mapping(carry,nd.x,i+offset,i+offset)};
        }
        // 自ノードの lazy を carry に積んでから、見かけ上右の子を優先して降りる。
        carry=composition(carry,nd.laz);
        auto ch=orderedChildren(v,sl,sr,d);

        // 見かけ上右の子を優先し、見つからなければ左の子へ進む。
        auto ret=LastLeaf(ch.high.cid,ch.high.sl,ch.high.sr,d-1,carry);
        if (ret.first!=-1) return ret;
        return LastLeaf(ch.low.cid,ch.low.sl,ch.low.sr,d-1,carry);
    }

    // 見かけ上の添字で a 以上にある生成済み葉のうち、最小のものを探す。
    // 戻り値:
    // {pos,val}     見つかった葉
    // {1LL<<B,e}    見つからない
    pair<ll,T> CeilLeaf(ll a,int v,ll sl,ll sr,ll d,F carry)const{
        if (v==-1) return {1LL<<B,e};

        ll l=storedBlockL(sl,d);
        ll r=storedBlockR(sl,d);

        // この部分木全体が a より左にあるなら候補なし。
        if (r<a) return {1LL<<B,e};

        // この部分木全体が a 以上なら、その中の最左葉が答え。
        if (a<=l) return FirstLeaf(v,sl,sr,d,carry);

        const Node &nd=node(v);
        if (d==0){
            return {l,mapping(carry,nd.x,l+offset,l+offset)};
        }

        carry=composition(carry,nd.laz);
        auto ch=orderedChildren(v,sl,sr,d);

        // ceil なので、見かけ上より左にある low 側を先に探す。
        auto ret=CeilLeaf(a,ch.low.cid,ch.low.sl,ch.low.sr,d-1,carry);
        if (ret.first!=(1LL<<B)) return ret;

        return CeilLeaf(a,ch.high.cid,ch.high.sl,ch.high.sr,d-1,carry);
    }

    // 見かけ上の添字で b 以下にある生成済み葉のうち、最大のものを探す。
    // 戻り値:
    // {pos,val}  見つかった葉
    // {-1,e}     見つからない
    pair<ll,T> FloorLeaf(ll b,int v,ll sl,ll sr,ll d,F carry)const{
        if (v==-1) return {-1,e};

        ll l=storedBlockL(sl,d);
        ll r=storedBlockR(sl,d);

        // この部分木全体が b より右にあるなら候補なし。
        if (b<l) return {-1,e};

        // この部分木全体が b 以下なら、その中の最右葉が答え。
        if (r<=b) return LastLeaf(v,sl,sr,d,carry);

        const Node &nd=node(v);
        if (d==0){
            // [l,r] が b をまたぐのは葉では起こらないが、統一的にここで返せる。
            return {l,mapping(carry,nd.x,l+offset,l+offset)};
        }

        // 子へ降りるときは carry に自ノード laz を積む。
        carry=composition(carry,nd.laz);
        auto ch=orderedChildren(v,sl,sr,d);

        // floor なので、見かけ上より右にある high 側を先に探す。
        auto ret=FloorLeaf(b,ch.high.cid,ch.high.sl,ch.high.sr,d-1,carry);
        if (ret.first!=-1) return ret;

        // high 側に候補がなければ low 側へ。
        return FloorLeaf(b,ch.low.cid,ch.low.sl,ch.low.sr,d-1,carry);
    }

    void ApplyRange(int v,ll a,ll b,ll sl,ll sr,ll d,cF &f){
        if (v==-1) return;

        ll l=storedBlockL(sl,d);
        ll r=storedBlockR(sl,d);
        if (r<a || b<l) return;

        if (a<=l && r<=b){
            if (v==rootid && node(v).nChild()==0) return;
            AllApply(v,f,sl,sr,d);
            return;
        }

        Push(v,sl,sr,d);
        ll sm=(sl+sr)>>1;
        ApplyRange(node(v).cids[0],a,b,sl,sm,d-1,f);
        ApplyRange(node(v).cids[1],a,b,sm+1,sr,d-1,f);
        Pull(v);
    }

    // a,b は見かけ上の添字
    // carry は祖先から降ってきた未伝播作用
    // 木は書き換えず、carry に積んで読む
    T Prod(ll a,ll b,int v,ll sl,ll sr,ll d,F carry)const{
        if (v==-1) return e;

        ll l=storedBlockL(sl,d);
        ll r=storedBlockR(sl,d);
        if (r<a || b<l) return e;

        const Node &nd=node(v);
        if (a<=l && r<=b){
            return mapping(carry,nd.x,l+offset,r+offset);
        }

        carry=composition(carry,nd.laz);
        auto ch=orderedChildren(v,sl,sr,d);

        T lx=Prod(a,b,ch.low.cid,ch.low.sl,ch.low.sr,d-1,carry);
        T rx=Prod(a,b,ch.high.cid,ch.high.sl,ch.high.sr,d-1,carry);
        return ope(lx,rx);
    }

    // isOK が「近くで false、遠くで true」のとき、左から最初の true を探す。
    // prePrd は「この部分木より左にある確定済み部分」の集約値。
    // carry は祖先からまだ子へ配っていない lazy。
    template<class IsOK> pair<ll,T> SearchR(
        ll a,int v,ll sl,ll sr,ll d,
        T prePrd,F carry,
        IsOK isOK,bool rev
    )const{
        ll l=storedBlockL(sl,d);
        ll r=storedBlockR(sl,d);
        if (r<a) return {r+1,prePrd};
        if (v==-1) return {r+1,prePrd};

        const Node &nd=node(v);

        // 部分木全体をまとめて採用したときの prefix 値。
        T whole=ope(prePrd,mapping(carry,nd.x,l+offset,r+offset));

        // この部分木が丸ごと「まだ条件を越えない」なら、葉まで降りずに打ち切る。
        if (a<=l && (bool)isOK(whole)==rev) return {r+1,whole};
        if (d==0) return {l,prePrd};

        carry=composition(carry,nd.laz);
        auto ch=orderedChildren(v,sl,sr,d);
        ll lowBlockR=storedBlockR(ch.low.sl,d-1);

        ll pos; T cur=prePrd;
        tie(pos,cur)=SearchR(a,ch.low.cid,ch.low.sl,ch.low.sr,d-1,cur,carry,isOK,rev);
        if (pos==lowBlockR+1){
            // low 側を全部読んでもまだ足りなければ high 側へ進む。
            tie(pos,cur)=SearchR(a,ch.high.cid,ch.high.sl,ch.high.sr,d-1,cur,carry,isOK,rev);
        }
        return {pos,cur};
    }

    // isOK が「近くで false、遠くで true」のとき、右から最初の true を探す。
    // prePrd は「この部分木より右にある確定済み部分」の集約値。
    template<class IsOK> pair<ll,T> SearchL(
        ll b,int v,ll sl,ll sr,ll d,
        T prePrd,F carry,
        IsOK isOK,bool rev
    )const{
        ll l=storedBlockL(sl,d);
        ll r=storedBlockR(sl,d);
        if (b<l) return {l-1,prePrd};
        if (v==-1) return {l-1,prePrd};

        const Node &nd=node(v);

        // 部分木全体をまとめて採用したときの suffix 値。
        T whole=ope(mapping(carry,nd.x,l+offset,r+offset),prePrd);

        if (r<=b && (bool)isOK(whole)==rev) return {l-1,whole};
        if (d==0) return {l,prePrd};

        carry=composition(carry,nd.laz);
        auto ch=orderedChildren(v,sl,sr,d);
        ll highBlockL=storedBlockL(ch.high.sl,d-1);

        ll pos; T cur=prePrd;
        tie(pos,cur)=SearchL(b,ch.high.cid,ch.high.sl,ch.high.sr,d-1,cur,carry,isOK,rev);
        if (pos==highBlockL-1){
            // high 側を全部読んでもまだ足りなければ low 側へ進む。
            tie(pos,cur)=SearchL(b,ch.low.cid,ch.low.sl,ch.low.sr,d-1,cur,carry,isOK,rev);
        }
        return {pos,cur};
    }
};
/*
- ノード未生成の部分は「データがない」とする(単位元のデータがあるとはしない)
- よって区間への操作時、ノード未生成の部分には何もしない
- offset、Bは広めにとる(広くしてもほとんど処理時間変わらない)
- xorAllIndex使用時は、opeは可換、mappingは座標非依存が前提
- offset と xorAllIndex の併用は不可

- ---- 定義 ---- (区間加算、区間max取得の例)
.                               ┌添字のビット数
.                  作用素型F┐  │  ┌データの単位元(実際の単位元でないとだめ)
.             データ型T┐   ↓  ↓  ↓ ┌作用素の単位元(使わない値ならOK)
lazyDynamicSegTree dsg(ll(),ll(),B,-INF,0,
    [](const T &x,const T &y){ return max(x,y); }, //op T(T,T)
    [](const F &f,const T &x,ll l,ll r){ return x+f; }, //[l,r]への作用 T(F,T,l,r)
    [](const F &g,const F &f){ return g+f; } //作用素合成 F(F,F) fの後gを作用
);

lazyDynamicSegTree dsg(T(),F(),B,e,id,ope,mapping,composition,offset);
.                           添字のoffset a[i-offset]に対応する ┘

- ---- 操作 ----
dsg.clear();       //空にする
ll i=dsg.imin();   //iの下限
ll i=dsg.imax();   //iの上限

dsg.set(i,x);      //a[i]←x 位置iにx代入、位置iがなければ新規作成
dsg.erase(i);      //位置iを削除
bool b=dsg.contains(i); //位置iが存在すればtrue

dsg.apply(i,f);    //a[i]←f(a[i])         位置iがなければ何もしない
dsg.apply(l,r,f);  //区間[l,r]内の既存データにだけfを作用

ll x=dsg[i];        //a[i] 位置iの値。未生成なら e
ll x=dsg.get(i);    //a[i] 位置iの値。未生成なら e
ll x=dsg.get(l,r);  //[l,r]の値
ll x=dsg.prod(l,r); //[l,r]の値
ll x=dsg.allprod(); //全区間の値

auto[j,va]=dsg.floor(i); //i以下の最大の生成済み位置と値。なければ {imin()-1,e}
auto[j,va]=dsg.ceil(i);  //i以上の最小の生成済み位置と値。なければ {imax()+1,e}
auto[j,va]=dsg.front();  //最小の生成済み位置と値。空なら {imax()+1,e}
auto[j,va]=dsg.back();   //最大の生成済み位置と値。空なら {imin()-1,e}

dsg.xorAllIndex(x);    //見かけ上の全添字に xor を掛ける

vpll ixs=dsg.enumerate(); //生成済み葉を位置昇順に列挙 {<位置i,値x>,…}
vll v=dsg.tov();          //長さ 2^B の配列化

- ---- 二分探索 ----
[L,R]内でラムダ式isOKが○(true)になる位置  L,Rは範囲外や逆転も可
未生成の点は e として扱われる

- 使用例
ll i=dsg.minRight(L,R,[&](ll x){ return x>=th; }); //            L×→×→×ⓡ○R
ll i=dsg.maxRight(L,R,[&](ll x){ return x<=th; }); //            L○→○→ⓡ××R
ll i=dsg.maxLeft (L,R,[&](ll x){ return x>=th; }); //L○ⓛ×←×←×R
ll i=dsg.minLeft (L,R,[&](ll x){ return x<=th; }); //L××ⓛ←○←○R

- 要件・挙動
minRight: isOK([L,r])=○(L≦r≦R)となる最左のr、ないときR+1  要件:isOK(e)=×
maxRight: isOK([L,r])=○(L≦r≦R)となる最右のr、ないときL-1  要件:isOK(e)=○
maxLeft:  isOK([l,R])=○(L≦l≦R)となる最右のl、ないときL-1  要件:isOK(e)=×
minLeft:  isOK([l,R])=○(L≦l≦R)となる最左のl、ないときR+1  要件:isOK(e)=○
*/


//pair用テンプレート
template<class T,class S> inline pair<T,S>& operator+=(pair<T,S> &a,const pair<T,S> &b){ a.first+=b.first; a.second+=b.second; return a; }
template<class T,class S> inline pair<T,S>& operator-=(pair<T,S> &a,const pair<T,S> &b){ a.first-=b.first; a.second-=b.second; return a; }
template<class T,class S> inline pair<T,S>& operator*=(pair<T,S> &a,const pair<T,S> &b){ a.first*=b.first; a.second*=b.second; return a; }
template<class T,class S> inline pair<T,S>& operator/=(pair<T,S> &a,const pair<T,S> &b){ a.first/=b.first; a.second/=b.second; return a; }
template<class T,class S> inline pair<T,S>& operator%=(pair<T,S> &a,const pair<T,S> &b){ a.first%=b.first; a.second%=b.second; return a; }
template<class T,class S,class R> inline pair<T,S>& operator+=(pair<T,S> &a,R b){ a.first+=b; a.second+=b; return a; }
template<class T,class S,class R> inline pair<T,S>& operator-=(pair<T,S> &a,R b){ a.first-=b; a.second-=b; return a; }
template<class T,class S,class R> inline pair<T,S>& operator*=(pair<T,S> &a,R b){ a.first*=b; a.second*=b; return a; }
template<class T,class S,class R> inline pair<T,S>& operator/=(pair<T,S> &a,R b){ a.first/=b; a.second/=b; return a; }
template<class T,class S,class R> inline pair<T,S>& operator%=(pair<T,S> &a,R b){ a.first%=b; a.second%=b; return a; }
template<class T,class S,class R> inline pair<T,S> operator+(const pair<T,S> &a,R b){ pair<T,S> c=a; return c+=b; }
template<class T,class S,class R> inline pair<T,S> operator-(const pair<T,S> &a,R b){ pair<T,S> c=a; return c-=b; }
template<class T,class S,class R> inline pair<T,S> operator*(const pair<T,S> &a,R b){ pair<T,S> c=a; return c*=b; }
template<class T,class S,class R> inline pair<T,S> operator/(const pair<T,S> &a,R b){ pair<T,S> c=a; return c/=b; }
template<class T,class S,class R> inline pair<T,S> operator%(const pair<T,S> &a,R b){ pair<T,S> c=a; return c%=b; }
template<class T,class S,class R> inline pair<T,S> operator-(R b,const pair<T,S> &a){ pair<T,S> c=-a; return c+=b; }
template<class T,class S> inline pair<T,S> operator-(const pair<T,S> &a,const pair<T,S> &b){ pair<T,S> c=a; return c-=b; }
template<class T,class S> inline pair<T,S> operator-(const pair<T,S> &a){ pair<T,S> c=a; return c*=(-1); }


auto solve(
    ll N,vll A
){
    A.push_back(0);
    /*
    現在位置iを左から右へ動かす
    keyは、左端をi+1としてあり得る右端それぞれの総xor値
    valueは、<右端個数c, xor=0にならずたまっている左方の個数s>
    (1)Ai>総xor値 のとき
        1手で0にできる。(1)の範囲のsの総和×1→ans、(1)の範囲のsに0代入
    //(2)Ai=総xor値 のとき
        //0手で0にできる。ansそのまま、(2)の範囲のsに0代入
    (3)Ai<総xor値 のとき
        Ai≧2＆A_{i+1}以降続く1の連続数が偶数個のとき→2手
        その他→1手
        (3)の範囲のsの総和×手数→ans、(3)の範囲のsへの代入なし

    i→i+1にする準備
        空区間を削除：key=0の右端個数cを1減らす
        左端を追加：全keyのsにcを足す
        総xor値から左端1つ削る：全keyにAi+1をxorする
    */
    
    vll ren1(N+1);//右方への1の連続数
    dep(i,N-1,0){
        if (A[i]==1)
            ren1[i]=ren1[i+1]+1;
    }

    using T=pll;//<個数,和>
    using F=pll;//<y=0/1,z> y=0:z代入,1:z加算

#if defined(_MSC_VER)
    ll B=4;
#else
    ll B=20;
#endif
    //                              ┌添字のビット数
    //                 作用素型F┐  │  ┌データの単位元(実際の単位元でないとだめ)
    //            データ型T┐   ↓  ↓  ↓      ┌作用素の単位元(使わない値ならOK)
    lazyDynamicSegTree sgt(T(), F(),B,pll(0,0),pll(2,0),
        [](const T &x,const T &y){ return x+y; }, //op T(T,T)
        [](const F &f,const T &x,ll l,ll r)->T
        {
            auto[c,s]=x;
            auto[y,z]=f;
            if (y==0)
                return {c,c*z};
            else
                return {c,s+c*z};
        }, //[l,r]への作用 T(F,T,l,r)
        [](const F &g,const F &f)->F
        {
            auto [y , z]=f;
            auto [yy,zz]=g;
            if (yy==0) //後が代入
                return {yy,zz};
            else
                return {y,z+zz};
        } //作用素合成 F(F,F) fの後gを作用
    );
    
    {//左端1の全区間の各総xor値をsgtにセット
        map<ll,ll> mp;
        ll smx=0;
        mp[smx]++;
        rep(i,1,N-1){
            smx^=A[i];
            mp[smx]++;
        }
        for (auto&&[key,ct]:mp){
            sgt.set(key,pll(ct,ct));
        }
    }


    ll ans=0;
    rep(i,0,N-1){
        //for (auto&& e: sgt.tov()) cout << e << '\n';

        ll ai=A[i];
        //(1)Ai>総xor値 のとき
        {
            auto [c,sm]= sgt.get(0,ai-1);
            ans+=sm*1;
            sgt.apply(0,ai-1,pll(0,0));
            //for (auto&& e: sgt.tov()) cout << e << '\n';
        }
        //(3)Ai<=総xor値 のとき
        {
            ll te= (ai>=2 and ren1[i+1]%2==0) ? 2 : 1;
            auto [c,sm]= sgt.get(ai,INF);
            ans+=sm*te;
        }
        //i→i+1にする準備
        {//空区間を削除：key=0の右端個数cを1減らす
            auto [c,s]=sgt[0];
            assert(c>0);
            if (c>1)
                sgt.set(0,pll(c-1,s));
            else
                sgt.erase(0);
        }
        //左端を追加：全keyのsにcを足す
        sgt.apply(0,INF,pll(1,1));
        //総xor値から左端1つ削る：全keyにAi+1をxorする
        sgt.xorAllIndex(A[i+1]);
    }
    //cout << ans << '\n';

    return ans;
}


auto solve2(
    ll N,vll A
){

    vll Ax=A;
    Ax.push_front(0);
    rep(i,1,N)
        Ax[i]^=Ax[i-1];
    auto cmx=[&](ll l,ll r){
        return Ax[r+1]^Ax[l];
    };

    auto ren1=[&](ll i,ll r){
        ll ret=0;
        rep(j,i,r-1){
            if (A[j]==1)
                ret++;
            else break;
        }
        return ret;
    };

    ll ans=0;
    rep(l,0,N-1) rep(r,l,N-1){
        ll sm=0;
        rep(i,l,r){
            ll ai=A[i];
            ll cx=cmx(i+1,r);
            if (ai>cx){
                sm++; break;
            }
            if (ai==1) sm++;
            else if (ren1(i+1,r)%2==1) sm++;
            else sm+=2;
        }
        ans+=sm;
    }

    return ans;
}

//#define RANDOM_TEST

#if defined(_MSC_VER)
#include <conio.h>
#endif
void solvecomp(
    ll N,vll A
){
    auto coutans=[](auto ans){
        cout << ans << '\n';
    };

    auto ans=solve(
        N,A
    );
    coutans(ans);
#if defined(RANDOM_TEST)
    cout << "- - - - -\n";
    auto an2=solve2(
        N,A
    );
    coutans(an2);
    cout << "================\n";
    if (ans!=an2){
        cout << "============ input =============\n";

        cout << N << '\n';
        cout << A << '\n';

        cout << "============ input end =========\n\n================\n";
#if defined(_MSC_VER)
        (void)_getch();
#endif
    }
#endif
}

void cin2solve(){
    auto N=cin1<ll>();
    auto A=cinv<ll>(N);

    solvecomp(
        N,A
    );
}



namespace RndSpace{
using Int = long long;
using dd = long double;
struct rndutil{
    mt19937 mt;
    rndutil(Int seed=0):mt(GetSeed(seed)){}
    Int val(Int a,Int b){ return mt()%(b-a+1)+a; }//[a,b]の乱数
    dd dval(){ return (dd)mt()/(1ll<<32); }//[0,1)の浮動小数点乱数
    vector<Int> ary(Int n,Int a,Int b){//長さnの配列、要素[a,b]内、重複可
        vector<Int> v(n);
        for (Int i=0; i<n; ++i) v[i]=this->val(a,b);
        return v;
    }
    vector<dd> dary(Int n){//長さnの[0,1)の浮動小数点乱数
        vector<dd> v(n);
        for (Int i=0; i<n; ++i) v[i]=this->dval();
        return v;
    }
    string str(Int n,char cs,char ce){//長さnのstring、使用文字cs~ce、重複可
        string str(n,cs);
        for (Int i=0; i<n; ++i) str[i]+=(char)this->val(0,ce-cs);
        return str;
    }
    vector<Int> sample(Int n,Int a,Int b){//長さnの配列、要素[a,b]内、重複無
        Int len=b-a+1;
        assert(n<=len);
        vector<Int> v(len);
        iota(v.begin(),v.end(),a);
        for (Int i=0; i<n; ++i) swap(v[i],v[this->val(i,len-1)]);
        v.resize(n);
        return v;
    }
    template <class T> auto sample(const T &v){//1つ選択
        return v[val(0,(Int)v.size()-1)];
    }
    template <class T> auto samplepop(T &v){//1つ取り出し(末尾swapし削除)
        Int i=val(0,(Int)v.size()-1);
        auto ret=v[i];
        v[i]=v.back();
        v.pop_back();
        return ret;
    }
    Int weightedSampleCore(const vector<Int> &cm){//重み付き乱択 累積和版
        Int randval=val(1,cm.back());
        return Int(lower_bound(cm.begin(),cm.end(),randval)-cm.begin());
    }
    Int weightedSample(const vector<Int> &pr){//重み付き乱択
        vector<Int> cm=pr;
        for (Int i=1; i<(Int)cm.size(); ++i) cm[i]+=cm[i-1];
        return weightedSampleCore(cm);
    }
    template <class T> void shuffle(T &v){//配列や文字列をシャッフル
        Int n=(Int)v.size();
        for (Int i=0; i<n; ++i) swap(v[i],v[this->val(i,n-1)]);
    }
    pair<Int,Int> range(Int a,Int b,Int m=1){ //[a,b]内閉区間長さm以上
        while (true){
            Int l=this->val(a,b+1),r=this->val(a,b+1);
            if (r-l<m)continue;
            return {l,r-1};
        }
    }
#if 1 //グラフ使用時ON
    vector<pair<Int,Int>> tree(Int N,bool zeroIndexed=false);
    vector<pair<Int,Int>> graph(
        Int N,Int M,bool isConnected,bool isDirected,bool zeroIndexed=false);
    vector<tuple<Int,Int,Int>> wgraph(Int N,Int M,Int cmin,Int cmax,
        bool isConnected,bool isDirected,bool zeroIndexed=false);
    template<class EDGES>
    EDGES GraphCore(Int N,Int M,bool isConnected,bool isDirected,bool zeroIndexed);
#endif
private:
    unsigned int GetSeed(Int seed){
        if (seed>=0) return (unsigned int)seed;
        return (unsigned int)chrono::system_clock::now().time_since_epoch().count();
    }
};
}//namespace
using RndSpace::rndutil;
/*
rndutil ru;
rndutil ru(-1); //seedランダム(時刻使用)
- -------- 整数x -------- 区間[a,b]
ll x=ru.val(a,b);
- -------- 浮動小数点数x -------- [0,1)
dd x=ru.dval();
- -------- 整数ベクトルv -------- 長さn,要素の区間[a,b] 配列重複有
vll v=ru.ary(n,a,b);
- -------- 整数ベクトルv -------- 長さn,要素の区間[a,b] 配列重複無
vll v=ru.sample(n,a,b);
- -------- 浮動小数点ベクトルv -------- 長さn,[0,1)
vdd v=ru.dary(n);
- -------- 文字列s -------- 長さn,使用文字'a'~'z'
string s=ru.str(n,'a','z');
- -------- 乱択 -------- vll,string等から1つ選択
ll   x=ru.sample(v);
char c=ru.sample(s);
- -------- 乱択削除 -------- vll,string等から1つ取り出し(末尾swapし削除)
ll x=ru.samplepop(v);
- -------- 重み付き乱択 -------- i∈{0,1,…,n-1}を重みwiで選択
ll i=ru.weightedSample(w);
ll i=ru.weightedSampleCore(cm);
.                          ↑wの累積和を与えることで高速に
- -------- シャッフル -------- vll,string等
ru.shuffle(a);
- -------- 範囲[l,r] --------  [l,r]⊆[a,b] 区間長1以上
auto[l,r]=ru.range(a,b);
auto[l,r]=ru.range(a,b,m);
.                      ↑区間長m以上
*/


void generand(){
    rndutil ru;

    rep(q,0,INF){
        ll N=ru.val(1,4);
        vll A=ru.ary(N,1,3);
        //vpll vu=ru.tree(n);

        solvecomp(
            N,A
        );
    }
}

}//SolvingSpace

//////////////////////////////////////////


int main(){
#if defined(RANDOM_TEST)
    SolvingSpace::cin2solve();
    SolvingSpace::generand();
#else
  #if 1
    //SolvingSpace::labo();'
    SolvingSpace::cin2solve();
  #else
    ll t;  cin >> t;
    rep(i,0,t-1){
        SolvingSpace::cin2solve();
    }
  #endif
#endif
    cerr << timeget() <<"ms"<< '\n';
    return 0;
}