来自FallDream的博客，未经允许，请勿转载，谢谢。
考虑用可持久化线段树直接维护每个点在不同时刻，第一辆车的编号。
这样3操作就变成了区间赋值，1操作变成区间和
2操作的话，只需要查询一下现在这辆车的编号，再到历史版本去查一下上一辆车的编号就行了。
#include<iostream>
#include<cstdio>
#define MN 500000
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,m,ty,rt[MN+],cnt=,num[MN+];
struct Tree{
int l,r,sum,val;
}T[MN*];
inline int newnode(int x,int flag=){if(flag)return x;T[++cnt]=T[x];return cnt;}
inline void Mark(int x,int len,int v){T[x].val=v;T[x].sum=len*num[v];}
inline void pushdown(int x,int lt,int rt)
{
int mid=lt+rt>>;
Mark(T[x].l=newnode(T[x].l),mid-lt+,T[x].val);Mark(T[x].r=newnode(T[x].r),rt-mid,T[x].val);T[x].val=;
} int Build(int l,int r)
{
int x=++cnt;
if(l!=r) T[x].l=Build(l,l+r>>),T[x].r=Build((l+r>>)+,r);
return x;
} int Query(int x,int l,int r,int lt,int rt)
{
if(l==lt&&r==rt) return T[x].sum;int mid=lt+rt>>;
if(T[x].val) pushdown(x,lt,rt);
if(r<=mid) return Query(T[x].l,l,r,lt,mid);
else if(l>mid) return Query(T[x].r,l,r,mid+,rt);
else return Query(T[x].l,l,mid,lt,mid)+Query(T[x].r,mid+,r,mid+,rt);
} int Query(int x,int k,int lt,int rt)
{
if(lt==rt) return T[x].val;int mid=lt+rt>>;
if(T[x].val) pushdown(x,lt,rt);
if(k>mid) return Query(T[x].r,k,mid+,rt);
else return Query(T[x].l,k,lt,mid);
} void Modify(int x,int l,int r,int lt,int rt,int v)
{
if(l==lt&&r==rt) {Mark(x,rt-lt+,v);return;}
int mid=lt+rt>>,flag=T[x].val;
if(T[x].val) pushdown(x,lt,rt);
if(r<=mid) Modify(T[x].l=newnode(T[x].l,flag),l,r,lt,mid,v);
else if(l>mid) Modify(T[x].r=newnode(T[x].r,flag),l,r,mid+,rt,v);
else Modify(T[x].l=newnode(T[x].l,flag),l,mid,lt,mid,v),
Modify(T[x].r=newnode(T[x].r,flag),mid+,r,mid+,rt,v);
T[x].sum=T[T[x].l].sum+T[T[x].r].sum;
}
int last=;
int main()
{
n=read();m=read();ty=read();rt[]=Build(,n);
for(int i=;i<=m;++i)
{
int op=read();rt[i]=newnode(rt[i-]);
if(op==) {int l=(read()+last*ty)%n+,r=(read()+last*ty)%n+;printf("%d\n",last=Query(rt[i],min(l,r),max(l,r),,n));}
if(op==) {int x=(read()+last*ty)%n+,y=Query(rt[i],x,,n);if(y!=) Modify(rt[i],x,x,,n,Query(rt[y-],x,,n));}
if(op==) {int l=(read()+last*ty)%n+,r=(read()+last*ty)%n+;num[i]=read();Modify(rt[i],min(l,r),max(l,r),,n,i);}
}
return ;
}