#include #include namespace my{ void main(); void solve(); } int main(){my::main();} namespace my{ #define eb emplace_back #define LL(...) ll __VA_ARGS__;lin(__VA_ARGS__) #define FO(n) for(ll ij=n;ij--;) #define FOR(i,...) for(auto[i,i##stop,i##step]=range(0,__VA_ARGS__);i1)x>>=1,++r;return r;} auto ceil(auto x,auto y){if(y<0)x=-x,y=-y;return x<=0?x/y:(x-1)/y+1;} templateconcept vectorial=is_base_of_v,V>; templateistream&operator>>(istream&i,vector&v){fe(v,e)i>>e;return i;} templateostream&operator<<(ostream&o,const vector&v){fe(v,e)o<?nl:sp);return o;} templatestruct vec:vector{ using vector::vector; vec(const vector&v){this->reserve(v.size());fe(v,e)this->eb(e);} vec&operator+=(const vec&u){vec&v=*this;fo(i,v.size())v[i]+=u[i];return v;} vec&operator-=(const vec&u){vec&v=*this;fo(i,v.size())v[i]-=u[i];return v;} vec&operator^=(const vec&u){this->insert(this->end(),u.begin(),u.end());return*this;} vec operator+(const vec&u)const{return vec{*this}+=u;} vec operator-(const vec&u)const{return vec{*this}-=u;} vec operator^(const vec&u)const{return vec{*this}^=u;} vec&operator++(){fe(*this,e)++e;return*this;} vec&operator--(){fe(*this,e)--e;return*this;} vec operator-()const{vec v=*this;fe(v,e)e=-e;return v;} vec slice(ll l,ll r)const{return vec(this->begin()+l,this->begin()+r);} }; void io(){cin.tie(nullptr)->sync_with_stdio(0);cout<>...>>a);} templatevoid pp(const auto&...a){ll n=sizeof...(a);((cout<0,c)),...);cout<struct dynamic_bitset{ static constexpr size_t block_size=sizeof(T)*CHAR_BIT; static constexpr size_t block_index(size_t i){return i>>log2_floor(block_size);} static constexpr size_t bit_index(size_t i){return i&(block_size-1);} vecbits; size_t n; size_t size()const{return n;} dynamic_bitset(size_t n):n(n),bits(ceil(n,block_size)){} dynamic_bitset(const string&s):n(s.size()),bits(ceil(s.size(),block_size)){fo(i,n)bits[block_index(i)]|=T(s[i]-'0')<&bits_proxy; size_t I; proxy(vec&bits_proxy,size_t I):bits_proxy(bits_proxy),I(I){} auto&operator=(bool f){ bits_proxy[block_index(I)]&=~(T(1)<auto&operator=(X x){return this->operator=(static_cast(x&1));} auto&operator=(const proxy&p){return this->operator=(static_cast(p));} operator bool()const{return bits_proxy[block_index(I)]>>bit_index(I)&1;} }; decltype(auto)operator[](size_t i){return proxy{bits,i};} decltype(auto)operator[](size_t i)const{return bits[block_index(i)]>>bit_index(i)&1;} auto&operator&=(const dynamic_bitset&b){fo(i,bits.size())bits[i]&=b.bits[i];return*this;} auto&operator|=(const dynamic_bitset&b){fo(i,bits.size())bits[i]|=b.bits[i];return*this;} auto&operator^=(const dynamic_bitset&b){fo(i,bits.size())bits[i]^=b.bits[i];return*this;} auto operator&(const dynamic_bitset&b)const{return dynamic_bitset{*this}&=b;} auto operator|(const dynamic_bitset&b)const{return dynamic_bitset{*this}|=b;} auto operator^(const dynamic_bitset&b)const{return dynamic_bitset{*this}^=b;} auto slice(ll l,ll r)const{ dynamic_bitset res(r-l); fo(bit_index(r-l)){ res[r-l-1]=(*this)[r-1]; --r; } ll upper_shift=bit_index(l); ll lower_shift=block_size-upper_shift; ll n=block_index(r-l); ll offset=block_index(l); fo(i,n){ if(upper_shift==0)res.bits[i]=bits[offset+i]; else res.bits[i]=(bits[offset+i]>>upper_shift)|(bits[offset+i+1]<>upper_shift); } } return*this; } auto&range_xor(ll l,const dynamic_bitset&p){ return range_bit_operation(bit_xor<>{},l,p); } string to_string()const{string s{};fo(i,size())s+=(*this)[i]+'0';return s;} friend istream&operator>>(istream&i,dynamic_bitset&db){string s;i>>s;db=s;return i;} friend ostream&operator<<(ostream&o,const dynamic_bitset&db){return o<