Subtask #1

直接用 vector 维护每个点 $4$ 个值有没有出现过。然后暴力改暴力插入删除就完了。

时间复杂度：$O(n^2V)$，空间复杂度：$O(nV)$。

Subtask #2

可以发现区间的集合全都加上一个数相当于让每一个数的位置平移若干位，而取模相当于把溢出的部分移到末尾。所以使用 bitset 位移优化即可。

不那么暴力也可以对每个集合打上懒标记处理，不过要麻烦得多。

时间复杂度：$O(n^2\frac{V}{w})$，空间复杂度：$O(n\frac{V}{w})$。

Subtask #3

插入删除操作让人想到平衡树，然后平衡树上每个点维护 $4$ 个权值即可。

块状链表当然也行，只不过会比较卡常。

时间复杂度：$O(nV\log n)$，空间复杂度：$O(nV)$。

Subtask #4

大量的区间操作并且不会改变数组长度，让人想到线段树，所以线段树上每个点维护一个 bitset。

但是有点不好处理懒标记，可以考虑先下放位移的，然后再下放添加与删除某个数的，具体实现见后文。

时间复杂度：$O(n\frac{V}{w}\log n)$，空间复杂度：$O(n\frac{V}{w})$。

Subtask #5

显然，对于这种既有插入删除又有区间操作的题目，普通平衡树和普通线段树都无法胜任，因此使用 WBLT 这种“平衡线段树”进行维护。写法与线段树类似，插入删除及平衡代码如下：

#include<bits/stdc++.h>
#define ll long long
#define gc getchar
#define pc putchar
#define sc scanf
#define pr printf
#define fu(v,s,e) for(int v=s;v<=(e);v++)
#define fd(v,s,e) for(int v=s;v>=(e);v--)
#define ciallo cerr<<"Ciallo~\n"
#define fuck cerr<<"Fuck you\n"
#define ___ cerr<<"----------------\n"
#define ___2 cerr<<"================\n"
#define mem(a,x) memset(a,x,sizeof(a))
#define itn int
#ifdef DEBUG
#define debug(...) __VA_ARGS__
#else
#define debug(...)
#endif
using namespace std;
#ifdef INFO
struct __info{~__info(){cerr<<'\n';___;cerr<<"Time: "<<1000.0*clock()/CLOCKS_PER_SEC<<" ms.\n";FILE* mem=fopen("/proc/self/status","r");char str[128];while(fgets(str,128,mem)!=NULL) if(strncmp(str,"VmRSS:",6)==0){cerr<<"Memory: "<<atoi(str+6)/1024.0<<" MB.\n";break;}}}_info_tmp;
#endif
inline int in(){char c=gc();int x=0,f=1;while((c<'0'||c>'9')&&c!='-') c=gc();if(c=='-') f=-1,c=gc();while(c>='0'&&c<='9') x=x*10+c-'0',c=gc();return x*f;}
int n,m,v;
namespace V_4{
    int lc[200005],rc[200005],sz[200005],pri[200005];
    bitset<4> s[200005],lz_and[200005],lz_or[200005],val[200005];
    int lz_b[200005],fg_and[200005],fg_or[200005];
    int tot,rt,_cnt;
    mt19937 rd((random_device())());
    inline int new_node(){
        tot++;
        lz_and[tot].set(),pri[tot]=rd(),sz[tot]=1;
        return tot;
    }
    inline void op_3(int u,int k){
        s[u]=(s[u]<<k)|(s[u]>>(v-k));
        val[u]=(val[u]<<k)|(val[u]>>(v-k));
        if(fg_and[u]) lz_and[u]=(lz_and[u]<<k)|(lz_and[u]>>(v-k));
        if(fg_or[u]) lz_or[u]=(lz_or[u]<<k)|(lz_or[u]>>(v-k));
        (lz_b[u]+=k)&=v-1;
    }
    inline void pushdown(int u){
        if(lz_b[u]) op_3(lc[u],lz_b[u]),op_3(rc[u],lz_b[u]),lz_b[u]=0;
        if(fg_and[u]){
            if(lc[u]){
                fg_and[lc[u]]=fg_or[lc[u]]=1;
                s[lc[u]]&=lz_and[u];
                val[lc[u]]&=lz_and[u];
                lz_and[lc[u]]&=lz_and[u];
                lz_or[lc[u]]&=lz_and[u];
            }
            if(rc[u]){
                fg_and[rc[u]]=fg_or[rc[u]]=1;
                s[rc[u]]&=lz_and[u];
                val[rc[u]]&=lz_and[u];
                lz_and[rc[u]]&=lz_and[u];
                lz_or[rc[u]]&=lz_and[u];
            }
            lz_and[u].set(),fg_and[u]=0;
        }
        if(fg_or[u]){
            if(lc[u]){
                fg_and[lc[u]]=fg_or[lc[u]]=1;
                s[lc[u]]|=lz_or[u];
                val[lc[u]]|=lz_or[u];
                lz_and[lc[u]]|=lz_or[u];
                lz_or[lc[u]]|=lz_or[u];
            }
            if(rc[u]){
                fg_and[rc[u]]=fg_or[rc[u]]=1;
                s[rc[u]]|=lz_or[u];
                val[rc[u]]|=lz_or[u];
                lz_and[rc[u]]|=lz_or[u];
                lz_or[rc[u]]|=lz_or[u];
            }
            lz_or[u].reset(),fg_or[u]=0;
        }
    }
    void down(int u){
        if(!u) return;
        pushdown(u);
        down(lc[u]);
        down(rc[u]);
    }
    inline void update(int u){
        s[u]=s[lc[u]]|s[rc[u]]|val[u];
        sz[u]=sz[lc[u]]+sz[rc[u]]+1;
    }
    void split(int u,int k,int &l,int &r){
        if(!u){
            l=r=0;
            return;
        }
        pushdown(u);
        if(k<=sz[lc[u]]){
            r=u;
            split(lc[u],k,l,lc[u]);
        }else{
            l=u;
            split(rc[u],k-sz[lc[u]]-1,rc[u],r);
        }
        update(u);
    }
    int merge(int l,int r){
        if(!l||!r) return l+r;
        if(pri[l]>pri[r]){
            pushdown(l);
            rc[l]=merge(rc[l],r);
            update(l);
            return l;
        }else{
            pushdown(r);
            lc[r]=merge(l,lc[r]);
            update(r);
            return r;
        }
    }
    inline void insert(int p){
        int a,b;
        split(rt,p-1,a,b);
        rt=merge(a,merge(new_node(),b));
    }
    inline void erase(int p){
        int a,b,c,tp;
        split(rt,p-1,a,tp);
        split(tp,1,b,c);
        rt=merge(a,c);
    }
    inline int query(int l,int r){
        int a,b,c,tp;
        split(rt,r,tp,c);
        split(tp,l-1,a,b);
        int res=(~s[b])._Find_first();
        rt=merge(a,merge(b,c));
        return res;
    }
    inline void op_1_1(int l,int r,int x){
        int a,b,c,tp;
        split(rt,r,tp,c);
        split(tp,l-1,a,b);
        fg_or[b]=1;
        s[b].set(x),lz_and[b].set(x),lz_or[b].set(x),val[b].set(x);
        rt=merge(a,merge(b,c));
    }
    inline void op_1_0(int l,int r,int x){
        int a,b,c,tp;
        split(rt,r,tp,c);
        split(tp,l-1,a,b);
        fg_and[b]=1;
        s[b].reset(x),lz_and[b].reset(x),lz_or[b].reset(x),val[b].reset(x);
        // down(b);
        rt=merge(a,merge(b,c));
    }
    inline void op_3(int l,int r,int x){
        int a,b,c,tp;
        split(rt,r,tp,c);
        split(tp,l-1,a,b);
        op_3(b,x);
        rt=merge(a,merge(b,c));
    }
    void print(const bitset<4> &s){
        int x=s._Find_first();
        // cerr<<'{';
        while(x<v) cerr<<x<<' ',x=s._Find_next(x);
        cerr<<'\n';
    }
    void print(int u){
        if(!u) return;
        pushdown(u);
        print(lc[u]);
        print(val[u]);
        print(rc[u]);
    }
    signed mian(){
        // freopen("Case_I_Test001.in","r",stdin);
        // freopen(".out","w",stdout);
        fu(i,1,n) insert(1);
        int op,tp,l,r,x;
        _cnt=n;
        while(m--){
            op=in();
            if(op==0){
                l=in(),r=in();
                debug(
                    ciallo;
                )
                pr("%d\n",query(l,r));
            }
            if(op==1){
                tp=in(),l=in(),r=in(),x=in();
                // assert(x<v);
                if(tp) op_1_1(l,r,x);
                else op_1_0(l,r,x);
            }
            if(op==2){
                tp=in(),x=in();
                if(tp) insert(x),_cnt++;
                else erase(x),_cnt--;
            }
            if(op==3){
                l=in(),r=in(),x=in()&(v-1);
                op_3(l,r,x);
            }
            debug(
                ___;
                print(rt);
                ___;
            )
            debug(
                assert(sz[rt]==_cnt);
            )
        }
        return 0;
    }
}
namespace V_1024{
    int lc[200005],rc[200005],sz[200005],pri[200005];
    bitset<1024> s[200005],lz_and[200005],lz_or[200005],val[200005];
    int lz_b[200005],fg_and[200005],fg_or[200005];
    int tot,rt,_cnt;
    mt19937 rd((random_device())());
    inline int new_node(){
        tot++;
        lz_and[tot].set(),pri[tot]=rd(),sz[tot]=1;
        return tot;
    }
    inline void op_3(int u,int k){
        s[u]=(s[u]<<k)|(s[u]>>(v-k));
        val[u]=(val[u]<<k)|(val[u]>>(v-k));
        if(fg_and[u]) lz_and[u]=(lz_and[u]<<k)|(lz_and[u]>>(v-k));
        if(fg_or[u]) lz_or[u]=(lz_or[u]<<k)|(lz_or[u]>>(v-k));
        (lz_b[u]+=k)&=v-1;
    }
    inline void pushdown(int u){
        if(lz_b[u]) op_3(lc[u],lz_b[u]),op_3(rc[u],lz_b[u]),lz_b[u]=0;
        if(fg_and[u]){
            if(lc[u]){
                fg_and[lc[u]]=fg_or[lc[u]]=1;
                s[lc[u]]&=lz_and[u];
                val[lc[u]]&=lz_and[u];
                lz_and[lc[u]]&=lz_and[u];
                lz_or[lc[u]]&=lz_and[u];
            }
            if(rc[u]){
                fg_and[rc[u]]=fg_or[rc[u]]=1;
                s[rc[u]]&=lz_and[u];
                val[rc[u]]&=lz_and[u];
                lz_and[rc[u]]&=lz_and[u];
                lz_or[rc[u]]&=lz_and[u];
            }
            lz_and[u].set(),fg_and[u]=0;
        }
        if(fg_or[u]){
            if(lc[u]){
                fg_and[lc[u]]=fg_or[lc[u]]=1;
                s[lc[u]]|=lz_or[u];
                val[lc[u]]|=lz_or[u];
                lz_and[lc[u]]|=lz_or[u];
                lz_or[lc[u]]|=lz_or[u];
            }
            if(rc[u]){
                fg_and[rc[u]]=fg_or[rc[u]]=1;
                s[rc[u]]|=lz_or[u];
                val[rc[u]]|=lz_or[u];
                lz_and[rc[u]]|=lz_or[u];
                lz_or[rc[u]]|=lz_or[u];
            }
            lz_or[u].reset(),fg_or[u]=0;
        }
    }
    void down(int u){
        if(!u) return;
        pushdown(u);
        down(lc[u]);
        down(rc[u]);
    }
    inline void update(int u){
        s[u]=s[lc[u]]|s[rc[u]]|val[u];
        sz[u]=sz[lc[u]]+sz[rc[u]]+1;
    }
    void split(int u,int k,int &l,int &r){
        if(!u){
            l=r=0;
            return;
        }
        pushdown(u);
        if(k<=sz[lc[u]]){
            r=u;
            split(lc[u],k,l,lc[u]);
        }else{
            l=u;
            split(rc[u],k-sz[lc[u]]-1,rc[u],r);
        }
        update(u);
    }
    int merge(int l,int r){
        if(!l||!r) return l+r;
        if(pri[l]>pri[r]){
            pushdown(l);
            rc[l]=merge(rc[l],r);
            update(l);
            return l;
        }else{
            pushdown(r);
            lc[r]=merge(l,lc[r]);
            update(r);
            return r;
        }
    }
    inline void insert(int p){
        int a,b;
        split(rt,p-1,a,b);
        rt=merge(a,merge(new_node(),b));
    }
    inline void erase(int p){
        int a,b,c,tp;
        split(rt,p-1,a,tp);
        split(tp,1,b,c);
        rt=merge(a,c);
    }
    inline int query(int l,int r){
        int a,b,c,tp;
        split(rt,r,tp,c);
        split(tp,l-1,a,b);
        int res=(~s[b])._Find_first();
        rt=merge(a,merge(b,c));
        return res;
    }
    inline void op_1_1(int l,int r,int x){
        int a,b,c,tp;
        split(rt,r,tp,c);
        split(tp,l-1,a,b);
        fg_or[b]=1;
        s[b].set(x),lz_and[b].set(x),lz_or[b].set(x),val[b].set(x);
        rt=merge(a,merge(b,c));
    }
    inline void op_1_0(int l,int r,int x){
        int a,b,c,tp;
        split(rt,r,tp,c);
        split(tp,l-1,a,b);
        fg_and[b]=1;
        s[b].reset(x),lz_and[b].reset(x),lz_or[b].reset(x),val[b].reset(x);
        // down(b);
        rt=merge(a,merge(b,c));
    }
    inline void op_3(int l,int r,int x){
        int a,b,c,tp;
        split(rt,r,tp,c);
        split(tp,l-1,a,b);
        op_3(b,x);
        rt=merge(a,merge(b,c));
    }
    void print(const bitset<1024> &s){
        int x=s._Find_first();
        // cerr<<'{';
        while(x<v) cerr<<x<<' ',x=s._Find_next(x);
        cerr<<'\n';
    }
    void print(int u){
        if(!u) return;
        pushdown(u);
        print(lc[u]);
        print(val[u]);
        print(rc[u]);
    }
    signed mian(){
        // freopen("Case_I_Test001.in","r",stdin);
        // freopen(".out","w",stdout);
        fu(i,1,n) insert(1);
        int op,tp,l,r,x;
        _cnt=n;
        while(m--){
            op=in();
            if(op==0){
                l=in(),r=in();
                debug(
                    ciallo;
                )
                pr("%d\n",query(l,r));
            }
            if(op==1){
                tp=in(),l=in(),r=in(),x=in();
                // assert(x<v);
                if(tp) op_1_1(l,r,x);
                else op_1_0(l,r,x);
            }
            if(op==2){
                tp=in(),x=in();
                if(tp) insert(x),_cnt++;
                else erase(x),_cnt--;
            }
            if(op==3){
                l=in(),r=in(),x=in()&(v-1);
                op_3(l,r,x);
            }
            debug(
                ___;
                print(rt);
                ___;
            )
            debug(
                assert(sz[rt]==_cnt);
            )
        }
        return 0;
    }
}
int main(){
    n=in(),m=in(),v=in();
    if(v==4) V_4::mian();
    if(v==1024) V_1024::mian();
    return 0;
}