struct segTree{
    ll size;
    vector<ll>tree;
    vector<ll>lazy;

    void init(ll n){
        tree.clear();
        size =1;
        while(size<n){
            size*=2;
        }
        tree.assign(2*size , 0);
        lazy.assign(2*size , -1);
    }

    //Node x : [lx rx] -->answer for this range

    void update(ll x ,ll lx ,ll rx , ll q_lx ,ll q_rx){
        if(q_lx <= lx && rx<=q_rx){
            if(lazy[x]==-1) lazy[x] = 1;
            else lazy[x]++;

            if(lazy[x]&1){
                tree[x] = (rx-lx+1) - tree[x];
            }

            if(rx!=lx){
                //push_downward
                if(lazy[2*x]!=-1) lazy[2*x] += lazy[x];
                else lazy[2*x] = lazy[x];
                if(lazy[2*x+1]!=-1) lazy[2*x+1] += lazy[x];
                else lazy[2*x+1] = lazy[x];
            }
            lazy[x] = -1;
            return;
        }

        if(q_lx > rx || q_rx < lx){
            if(lazy[x]!=-1 && (lazy[x]&1)){
                tree[x] = (rx-lx+1) - tree[x];
            }
            if(lazy[x]!=-1 && rx!=lx){
                //push_downward
                if(lazy[2*x]!=-1) lazy[2*x] += lazy[x];
                else lazy[2*x] = lazy[x];
                if(lazy[2*x+1]!=-1) lazy[2*x+1] += lazy[x];
                else lazy[2*x+1] = lazy[x];
            }
            lazy[x] = -1;
            return;
        }

        if(lazy[x]!=-1){
            //push the information that you toggle your bits
            if(lazy[2*x]!=-1) lazy[2*x] += lazy[x];
            else lazy[2*x] = lazy[x];
            if(lazy[2*x+1]!=-1) lazy[2*x+1] += lazy[x];
            else lazy[2*x+1] = lazy[x];
            lazy[x] = -1;
        }

        ll mid = (lx +rx)>>1;
        update(2*x , lx , mid , q_lx , q_rx );
        update(2*x+1 , mid+1 , rx , q_lx , q_rx );
        tree[x] = tree[2*x] + tree[2*x+1];
    }

    void update(ll q_lx , ll q_rx){
        update(1 , 0 , size-1 , q_lx , q_rx);
    }

    ll query(ll x ,ll lx ,ll rx , ll q_lx , ll q_rx){
        if(q_lx <= lx && rx<=q_rx){
            if(lazy[x]!=-1 && (lazy[x]&1)){
                tree[x] = (rx-lx+1) - tree[x];
            }
            if(lazy[x]!=-1 && rx!=lx){
                //push_downward
                if(lazy[2*x]!=-1) lazy[2*x] += lazy[x];
                else lazy[2*x] = lazy[x];
                if(lazy[2*x+1]!=-1) lazy[2*x+1] += lazy[x];
                else lazy[2*x+1] = lazy[x];
            }
            lazy[x] = -1;
            return tree[x];
        }

        if(q_lx > rx || q_rx < lx){
            if(lazy[x]!=-1 && (lazy[x]&1)){
                tree[x] = (rx-lx+1) - tree[x];
            }
            if(lazy[x]!=-1 && rx!=lx){
                //push_downward
                if(lazy[2*x]!=-1) lazy[2*x] += lazy[x];
                else lazy[2*x] = lazy[x];
                if(lazy[2*x+1]!=-1) lazy[2*x+1] += lazy[x];
                else lazy[2*x+1] = lazy[x];
            }
            lazy[x] = -1;
            return 0;
        }

        if(lazy[x]!=-1){
            //push the information that you toggle your bits
            if(lazy[2*x]!=-1) lazy[2*x] += lazy[x];
            else lazy[2*x] = lazy[x];
            if(lazy[2*x+1]!=-1) lazy[2*x+1] += lazy[x];
            else lazy[2*x+1] = lazy[x];
            lazy[x] = -1;
        }

        ll mid = (lx +rx)>>1;

        ll val1 = query(2*x , lx , mid , q_lx , q_rx );
        ll val2 = query(2*x+1 , mid+1 , rx , q_lx , q_rx );
        tree[x] = tree[2*x] + tree[2*x+1];
        return val1 + val2;
    }

    ll query(ll q_lx , ll q_rx){
        return query(1 , 0 , size-1 , q_lx , q_rx);
    }

};