#include #include using namespace std; using ll = long long; class LinkCutTree { struct Node { Node *l, *r, *p; int key; long long sum; bool rev; explicit Node() : key(0), sum(0), rev(false), l(nullptr), r(nullptr), p(nullptr) {} bool is_root() const { return not p or (p->l != this and p->r != this); } }; void update(Node* t) { t->sum = t->key; if(t->l) t->sum += t->l->sum; if(t->r) t->sum += t->r->sum; } void rotate_right(Node* t) { Node *x = t->p, *y = x->p; if((x->l = t->r)) t->r->p = x; t->r = x, x->p = t; update(x), update(t); if((t->p = y)) { if(y->l == x) y->l = t; if(y->r == x) y->r = t; update(y); } } void rotate_left(Node* t) { Node *x = t->p, *y = x->p; if((x->r = t->l)) t->l->p = x; t->l = x, x->p = t; update(x), update(t); if((t->p = y)) { if(y->l == x) y->l = t; if(y->r == x) y->r = t; update(y); } } void toggle(Node* t) { std::swap(t->l, t->r); t->rev ^= true; } void push(Node* t) { if(t->rev) { if(t->l) toggle(t->l); if(t->r) toggle(t->r); t->rev = false; } } void splay(Node *t) { push(t); while(not t->is_root()) { Node* q = t->p; if(q->is_root()) { push(q), push(t); q->l == t ? rotate_right(t) : rotate_left(t); } else { Node* r = q->p; push(r), push(q), push(t); if(r->l == q) { if(q->l == t) rotate_right(q), rotate_right(t); else rotate_left(t), rotate_right(t); } else { if(q->r == t) rotate_left(q), rotate_left(t); else rotate_right(t), rotate_left(t); } } } } std::vector Node_info; public: int N; LinkCutTree(int n) : N(n), Node_info(n) { for(int i = 0; i < N; i++){ Node_info[i] = new Node(); } } //vと根との間を Heavy-edge で繋げてvを木の根にする void expose(int v) { Node* t = Node_info[v]; Node* rp = nullptr; for(Node* cur = t; cur; cur = cur->p) { splay(cur); cur->r = rp; update(cur); rp = cur; } splay(t); } //vをもともの木の根にする void evert(int v) { expose(v); toggle(Node_info[v]); push(Node_info[v]); } void link(int _child, int _parent) { Node *child = Node_info[_child], *parent = Node_info[_parent]; evert(_child), expose(_parent); child->p = parent; parent->r = child; update(parent); } void cut(int _child) { Node *child = Node_info[_child]; expose(_child); auto *parent = child->l; child->l = nullptr; parent->p = nullptr; } long long query(int u, int v) { evert(u); expose(v); return Node_info[v]->sum; } void set(int p, int v) { expose(p); Node_info[p]->key = v; update(Node_info[p]); } }; int main() { ios::sync_with_stdio(false); cin.tie(0); int N, Q; ll X; cin >> N >> X >> Q; LinkCutTree LCT(N + Q); atcoder::dsu uf(N); vector dia(N); vector> sv(N); for(int i = 0; i < N; i++) sv[i] = {i, i}; auto update_diameter = [&](int x, int y){ ll mx; int u, v; if(dia[x] >= dia[y]){ mx = dia[x], u = sv[x][0], v = sv[x][1]; }else{ mx = dia[y], u = sv[y][0], v = sv[y][1]; } for(int i = 0; i < 2; i++){ for(int j = 0; j < 2; j++){ ll d = LCT.query(sv[x][i], sv[y][j]); if(d > mx){ mx = d, u = sv[x][i], v = sv[y][j]; } } } int r = uf.merge(x, y); dia[r] = mx; sv[r] = {u, v}; }; int type, v, u, w; for(int i = 0; i < Q; i++){ cin >> type; if(type == 1){ cin >> v >> w; LCT.link(v, i + N); LCT.link(X, i + N); LCT.set(i + N, w); update_diameter(uf.leader(v), uf.leader(X)); }else if(type == 2){ cin >> v >> u; if(!uf.same(v, u)){ cout << -1 << '\n'; continue; } ll d = LCT.query(v, u); (X += d) %= N; cout << d << '\n'; }else if(type == 3){ cin >> v; cout << dia[uf.leader(v)] << '\n'; }else{ cin >> v; X += v; if(X >= N) X -= N; } } }