#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define allof(obj) (obj).begin(), (obj).end() #define range(i, l, r) for(int i=l;i>1)|y_bit)) #define bit_kth(i, k) ((i >> k)&1) #define bit_highest(i) (i?63-__builtin_clzll(i):-1) #define bit_lowest(i) (i?__builtin_ctzll(i):-1) #define sleepms(t) std::this_thread::sleep_for(std::chrono::milliseconds(t)) using ll = long long; using ld = long double; using ul = uint64_t; using pi = std::pair; using pl = std::pair; using namespace std; template std::ostream &operator << (std::ostream &dest, const std::pair &p) { dest << p.first << ' ' << p.second; return dest; } template std::ostream &operator << (std::ostream &dest, const std::tuple &t) { dest << std::get<0>(t) << ' ' << std::get<1>(t); return dest; } template std::ostream &operator << (std::ostream &dest, const std::tuple &t) { dest << std::get<0>(t) << ' ' << std::get<1>(t) << ' ' << std::get<2>(t); return dest; } template std::ostream &operator << (std::ostream &dest, const std::tuple &t) { dest << std::get<0>(t) << ' ' << std::get<1>(t) << ' ' << std::get<2>(t) << ' ' << std::get<3>(t); return dest; } template std::ostream &operator << (std::ostream &dest, const std::vector> &v) { int sz = v.size(); if (!sz) return dest; for (int i = 0; i < sz; i++) { int m = v[i].size(); for (int j = 0; j < m; j++) dest << v[i][j] << (i != sz - 1 && j == m - 1 ? '\n' : ' '); } return dest; } template std::ostream &operator << (std::ostream &dest, const std::vector &v) { int sz = v.size(); if (!sz) return dest; for (int i = 0; i < sz - 1; i++) dest << v[i] << ' '; dest << v[sz - 1]; return dest; } template std::ostream &operator << (std::ostream &dest, const std::array &v) { if (!sz) return dest; for (int i = 0; i < sz - 1; i++) dest << v[i] << ' '; dest << v[sz - 1]; return dest; } template std::ostream &operator << (std::ostream &dest, const std::set &v) { for (auto itr = v.begin(); itr != v.end();) { dest << *itr; itr++; if (itr != v.end()) dest << ' '; } return dest; } template std::ostream &operator << (std::ostream &dest, const std::map &v) { for (auto itr = v.begin(); itr != v.end(); ) { dest << '(' << itr->first << ", " << itr->second << ')'; itr++; if (itr != v.end()) dest << '\n'; } return dest; } template vector make_vec(size_t sz, T val) { return std::vector(sz, val); } template auto make_vec(size_t sz, Tail ...tail) { return std::vector(tail...))>(sz, make_vec(tail...)); } template vector read_vec(size_t sz) { std::vector v(sz); for (int i = 0; i < (int)sz; i++) std::cin >> v[i]; return v; } template auto read_vec(size_t sz, Tail ...tail) { auto v = std::vector(tail...))>(sz); for (int i = 0; i < (int)sz; i++) v[i] = read_vec(tail...); return v; } // x / y以上の最小の整数 ll ceil_div(ll x, ll y) { assert(y > 0); return (x + (x > 0 ? y - 1 : 0)) / y; } // x / y以下の最大の整数 ll floor_div(ll x, ll y) { assert(y > 0); return (x + (x > 0 ? 0 : -y + 1)) / y; } void io_init() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); } #include // サイズは空白や改行も含めた文字数 template struct fast_io { char ibuf[size_in], obuf[size_out]; char *ip, *op; fast_io() : ip(ibuf), op(obuf) { int t = 0, k = 0; while ((k = read(STDIN_FILENO, ibuf + t, sizeof(ibuf) - t)) > 0) { t += k; } } ~fast_io() { int t = 0, k = 0; while ((k = write(STDOUT_FILENO, obuf + t, op - obuf - t)) > 0) { t += k; } } long long in() { long long x = 0; bool neg = false; for (; *ip < '+'; ip++) ; if (*ip == '-'){ neg = true; ip++;} else if (*ip == '+') ip++; for (; *ip >= '0'; ip++) x = 10 * x + *ip - '0'; if (neg) x = -x; return x; } unsigned long long inu64() { unsigned long long x = 0; for (; *ip < '+'; ip++) ; if (*ip == '+') ip++; for (; *ip >= '0'; ip++) x = 10 * x + *ip - '0'; return x; } char in_char() { for (; *ip < '!'; ip++) ; return *ip++; } void out(long long x, char c = 0) { static char tmp[20]; if (!x) { *op++ = '0'; } else { int i; if (x < 0) { *op++ = '-'; x = -x; } for (i = 0; x; i++) { tmp[i] = x % 10; x /= 10; } for (i--; i >= 0; i--) *op++ = tmp[i] + '0'; } if (c) *op++ = c; } void outu64(unsigned long long x, char c = 0) { static char tmp[20]; if (!x) { *op++ = '0'; } else { int i; for (i = 0; x; i++) { tmp[i] = x % 10; x /= 10; } for (i--; i >= 0; i--) *op++ = tmp[i] + '0'; } if (c) *op++ = c; } void out_char(char x, char c = 0){ *op++ = x; if (c) *op++ = c; } long long memory_size() { return (long long)(size_in + size_out) * sizeof(char); } }; template struct erasable_heap { std::priority_queue> pq, del; void push(T x) { pq.push(x); } // xがpushされていないと壊れる void erase(T x) { del.push(x); } void modify() { while (!del.empty() && pq.top() == del.top()) { pq.pop(); del.pop(); } } int size() { return pq.size() - del.size(); } T max() { modify(); return pq.top(); } T pop_max() { modify(); T res = pq.top(); pq.pop(); return res; } }; template struct centroid_dynamic { struct T { W distsum, distsum_rev, w, wsum, len, lensum; T() : distsum(0), distsum_rev(0), w(0), wsum(0), len(0), lensum(0) {} }; struct U { W distsum, wsum; U() : distsum(0), wsum(0) {} }; struct node { node *lch, *rch, *par; bool _flip; T x; U y; erasable_heap> h; node() : lch(nullptr), rch(nullptr), par(nullptr), _flip(false), x(), y() {} bool is_root() { return !par || (par->lch != this && par->rch != this); } }; // 重みwの頂点 static node *make_node(W w) { node *v = new node(); v->x.w = v->x.wsum = w; return v; } // 長さlenの辺 static node *make_edge(W len) { node *v = new node(); v->x.len = v->x.lensum = len; return v; } static void update(node *v) { T lsum = (v->lch ? v->lch->x : T()); T rsum = (v->rch ? v->rch->x : T()); W a = lsum.distsum + lsum.lensum * v->x.w; W b = lsum.wsum + v->x.w; W c = lsum.lensum + v->x.len; W d = v->y.distsum + rsum.distsum; W e = v->y.wsum + rsum.wsum; v->x.distsum = a + d + c * e; v->x.distsum_rev = (rsum.distsum_rev + rsum.lensum * v->x.w) + (v->y.distsum + lsum.distsum_rev) + (rsum.lensum + v->x.len) * (v->y.wsum + lsum.wsum); v->x.wsum = b + e; v->x.lensum = c + rsum.lensum; } static void flip(node *v) { v->_flip = !v->_flip; std::swap(v->x.distsum, v->x.distsum_rev); std::swap(v->lch, v->rch); } static void push(node *v) { if (v->_flip) { if (v->lch) flip(v->lch); if (v->rch) flip(v->rch); v->_flip = false; } } // 直前の根を返す static node *splay(node *v) { node *u = v; push(v); while (!v->is_root()) { node *p = v->par; if (p->is_root()) { u = p; push(p), push(v); node *pp = p->par; if(p->lch == v) { if ((p->lch = v->rch)) p->lch->par = p; update(p); v->rch = p; p->par = v; update(v); } else { if ((p->rch = v->lch)) p->rch->par = p; update(p); v->lch = p; p->par = v; update(v); } v->par = pp; } else { node *pp = p->par; node *ppp = pp->par; if (pp->is_root()) u = pp; push(pp), push(p), push(v); if (pp->lch == p) { if (p->lch == v) { if ((pp->lch = p->rch)) pp->lch->par = pp; update(pp); p->rch = pp; pp->par = p; if ((p->lch = v->rch)) p->lch->par = p; update(p); v->rch = p; p->par = v; update(v); } else { if ((p->rch = v->lch)) p->rch->par = p; update(p); if ((pp->lch = v->rch)) pp->lch->par = pp; update(pp); v->lch = p; v->rch = pp; p->par = pp->par = v; update(v); } } else { if(p->rch == v) { if ((pp->rch = p->lch)) pp->rch->par = pp; update(pp); p->lch = pp; pp->par = p; if ((p->rch = v->lch)) p->rch->par = p; update(p); v->lch = p; p->par = v; update(v); } else { if ((p->lch = v->rch)) p->lch->par = p; update(p); if ((pp->rch = v->lch)) pp->rch->par = pp; update(pp); v->rch = p; v->lch = pp; p->par = pp->par = v; update(v); } } if ((v->par = ppp)) { if (ppp->lch == pp) ppp->lch = v; if (ppp->rch == pp) ppp->rch = v; } } } return u; } static node* expose(node *v) { node *c = nullptr; node *pr = nullptr; W wsum = 0; for (node *u = v; u; u = u->par) { node *pr_tmp = splay(u); W wsum_tmp = u->x.wsum; if (c) { u->y.distsum -= c->x.distsum; u->y.wsum -= c->x.wsum; u->h.erase({wsum, pr}); } node *r = u->rch; if (r) { u->y.distsum += r->x.distsum; u->y.wsum += r->x.wsum; u->h.push({r->x.wsum, r}); } u->rch = c; update(u); c = u; pr = pr_tmp; wsum = wsum_tmp; } splay(v); return c; } // vを根にする static void evert(node *v) { expose(v); flip(v); } // 非連結であることが保証されている場合 static void _link(node *p, node *c) { evert(c); expose(p); c->par = p; p->rch = c; update(p); } // cの親との辺を切る static void cut_from_parent(node *c){ expose(c); node *p = c->lch; if (p == nullptr) return; c->lch = p->par = nullptr; update(c); } // 辺(a, b)があることが保証されている場合 static void _cut(node *u, node *v) { evert(u); cut_from_parent(v); } // 連結なことが保証されている場合 static node *_lca(node *u, node *v) { expose(u); return expose(v); } static bool is_there_edge(node *u, node *v) { evert(u); return u == get_parent(v); } static node *get_root(node *v) { expose(v); while (v->lch) { push(v); v = v->lch; } splay(v); return v; } static node *get_parent(node *v) { expose(v); if (!v->lch) return nullptr;// aが根 push(v); v = v->lch; while (v->rch) { push(v); v = v->rch; } splay(v); return v; } // 同じ連結成分か static bool is_same(node *u, node *v) { if (!u || !v) return false; return get_root(u) == get_root(v); } static node *centroid(node *v) { expose(v); W wsum = v->x.wsum; if (wsum == 0) return v; while (true) { W subsum = 0; node *u = nullptr; while (v) { push(v); W rsum = v->x.w + v->y.wsum + subsum + (v->rch ? v->rch->x.wsum : 0); if (wsum <= 2 * rsum) { u = v; v = v->rch; } else { v = v->lch; subsum = rsum; } } v = u; if (v->h.size() == 0 || 2 * v->h.max().first <= wsum) { expose(v); return v; } v = v->h.max().second; splay(v); } } }; int main() { fast_io<1 << 25, 1 << 24> io; int N = io.in(); int Q = io.in(); using tree = centroid_dynamic; using node = tree::node; std::vector V(N); for (int i = 0; i < N; i++) V[i] = tree::make_node(1); map, node*> mp; long long S = 0; for (int i = 0; i < Q; i++) { int t = io.in(); if (t == 1) { int a = io.in(); int b = io.in(); int c = io.in(); a = (a - 1 + S) % N; b = (b - 1 + S) % N; auto e = tree::make_edge(c); if (a > b) std::swap(a, b); mp[{a, b}] = e; tree::_link(V[a], e); tree::_link(V[b], e); } else if (t == 2) { int a = io.in(); int b = io.in(); a = (a - 1 + S) % N; b = (b - 1 + S) % N; if (a > b) std::swap(a, b); auto e = mp[{a, b}]; tree::_cut(V[a], e); tree::_cut(e, V[b]); } else { int a = io.in(); a = (a - 1 + S) % N; bool f = V[a]->x.w; tree::expose(V[a]); V[a]->x.w = !f; tree::update(V[a]); auto v = tree::centroid(V[a]); tree::evert(v); long long ans = v->x.distsum; io.out(ans, '\n'); S = (S + ans) % N; } } }