#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; struct LinkCutTree{ struct Node{ Node *l, *r, *p; bool rev; int idx, val, sz, szl; ll cost, sum, suml, costs, sum2; set> dat; Node(int val, int idx, ll cost):cost(cost), costs(cost), sum(0), sum2(0), suml(0), idx(idx), val(val), sz(val), szl(0), rev(false), l(nullptr), r(nullptr), p(nullptr){} bool is_root(){ return !p || (p->l!=this && p->r!=this); } }; vector v; LinkCutTree(int n){ v.resize(n); for(int i=0; isum, t->sum2); swap(t->l, t->r); t->rev^=true; } void push(Node *t){ if(!t) return; if(t->rev){ toggle(t->l); toggle(t->r); t->rev=false; } } void update(Node *t){ t->sz=t->val+t->szl, t->costs=t->cost; if(t->l) t->sz+=t->l->sz, t->costs+=t->l->costs; if(t->r) t->sz+=t->r->sz, t->costs+=t->r->costs; t->sum=t->suml+t->cost*t->szl; t->sum2=t->suml+t->cost*t->szl; if(t->l) t->sum+=t->l->sum, t->sum2+=t->l->sum2, t->sum+=t->l->costs*(t->val+t->szl), t->sum2+=t->l->sz*t->cost; if(t->r) t->sum+=t->r->sum, t->sum2+=t->r->sum2, t->sum+=t->r->sz*t->cost, t->sum2+=t->r->costs*(t->val+t->szl); if(t->l && t->r) t->sum+=t->l->costs*t->r->sz, t->sum2+=t->r->costs*t->l->sz; } void rotate(Node *t){ Node *p=t->p, *pp=p->p, *ch; if(p->l==t) ch=t->r; else ch=t->l; if(pp){ if(pp->l==p) pp->l=t; else if(pp->r==p) pp->r=t; else{ pp->dat.erase({p->sz, p->idx}); pp->dat.insert({p->sz, t->idx}); } } t->p=pp; if(p->l==t) t->r=p; else t->l=p; p->p=t; if(p->l==t) p->l=ch; else p->r=ch; if(ch) ch->p=p; update(p); update(t); } int state(Node *t){ if(t->is_root()) return 0; else if(t->p->l==t) return 1; else return -1; } void splay(Node *t){ push(t); while(state(t)){ if(!state(t->p)){ push(t->p); push(t); rotate(t); }else{ push(t->p->p); push(t->p); push(t); if(state(t->p)==state(t)){ rotate(t->p); rotate(t); }else{ rotate(t); rotate(t); } } } } Node *expose(Node *t){ Node *rp=nullptr; for(Node *now=t; now; now=now->p){ splay(now); if(rp){ now->dat.erase({rp->sz, rp->idx}); now->szl-=rp->sz; now->suml-=rp->sum; } if(now->r){ now->dat.insert({now->r->sz, now->r->idx}); now->szl+=now->r->sz; now->suml+=now->r->sum; } now->r=rp; update(now); rp=now; } splay(t); return rp; } void link(Node *c, Node *p){ expose(c); expose(p); p->r=c; c->p=p; update(p); } void cut(Node *c){ expose(c); c->l->p=nullptr; c->l=nullptr; update(c); } void evert(Node *t){ expose(t); toggle(t); push(t); } Node *find(Node *t){ evert(t); int n=t->sz, m=(n+1)/2; if(n==0) return t; Node *now=t; while(1){ push(now); if(now->r && now->r->sz>=m) now=now->r; else if((now->r?now->r->sz:0)+now->szl+now->valr?now->r->sz:0)+now->szl+now->val; now=now->l; }else{ if(now->dat.empty() || (*now->dat.rbegin()).first<=n/2) return now; else{ m=(n+1)/2; now=v[(*now->dat.rbegin()).second]; } } } } }; int main() { int n, q; scanf("%d %d", &n, &q); LinkCutTree lct(n); using node=LinkCutTree::Node; ll s=0; int k=n; int a1[300030]; while(q--){ int t; scanf("%d", &t); if(t==1){ int a, b, c; scanf("%d %d %d", &a, &b, &c); a=(a-1+s)%n, b=(b-1+s)%n; node *e=new node(0, k, c); a1[k]=a; k++; lct.v.push_back(e); lct.link(e, lct.v[a]); lct.evert(e); lct.link(e, lct.v[b]); }else if(t==2){ int a, b; scanf("%d %d", &a, &b); a=(a-1+s)%n, b=(b-1+s)%n; lct.evert(lct.v[a]); lct.expose(lct.v[b]); lct.cut(lct.v[b]); }else{ int a; scanf("%d", &a); a=(a-1+s)%n; lct.expose(lct.v[a]); lct.v[a]->val^=1; node *g=lct.find(lct.v[a]); if(g->idx>=n) g=lct.v[a1[g->idx]]; lct.evert(g); ll ans=g->sum; printf("%lld\n", ans); (s+=ans)%=n; } } return 0; }