#include using namespace std; using ll = long long; struct problem_H { int MAX_LOGV, N; vector>> G; vector> parent; vector dp; vector depth; vector parent_or_size; vector diameter; vector> diameter_vertex; queue que; problem_H(int n) : N(n) { MAX_LOGV = __lg(N) + 1; G.resize(N); parent.resize(MAX_LOGV, vector(N, -1)); parent_or_size.resize(N, -1); dp.resize(N), depth.resize(N); diameter.resize(N); diameter_vertex.resize(N); for(int i = 0; i < N; i++) diameter_vertex[i] = {i, i}; } int leader(int v){ return parent_or_size[v] < 0 ? v : parent_or_size[v]; } void merge(int u, int v, int w){ int x = leader(u), y = leader(v); if(-parent_or_size[x] < -parent_or_size[y]) { swap(x, y); swap(u, v); } parent_or_size[x] += parent_or_size[y]; G[u].emplace_back(v, w); G[v].emplace_back(u, w); update_parent(v, u, w); que.emplace(v); while(!que.empty()){ v = que.front(); que.pop(); parent_or_size[v] = x; for(auto &edge : G[v]){ tie(u, w) = edge; if(parent[0][v] == u) continue; update_parent(u, v, w); que.emplace(u); } } update_diameter(x, y); } void update_parent(int &v, int &par, int &w){ parent[0][v] = par; depth[v] = depth[par] + 1; dp[v] = dp[par] + w; int depth_log = __lg(max(1, depth[v])); for(int i = 0; i < depth_log; i++){ parent[i + 1][v] = parent[i][v] == -1 ? -1 : parent[i][parent[i][v]]; } } void update_diameter(int &x, int &y){ ll mx; int u, v; if(diameter[x] >= diameter[y]) { mx = diameter[x]; u = diameter_vertex[x][0], v = diameter_vertex[x][1]; } else { mx = diameter[y]; u = diameter_vertex[y][0], v = diameter_vertex[y][1]; } for(int i = 0; i < 2; i++){ int v1 = diameter_vertex[x][i]; for(int j = 0; j < 2; j++){ int v2 = diameter_vertex[y][j]; ll d = dist(v1, v2); if(d > mx){ mx = d; u = v1, v = v2; } } } diameter[x] = mx; diameter_vertex[x] = {u, v}; } long long dist(int u, int v){ if(leader(u) != leader(v)) return -1; if(depth[v] < depth[u]) swap(v, u); long long res = dp[u] + dp[v]; int d = depth[v] - depth[u]; while(d){ v = parent[__lg(d & -d)][v]; d -= d & -d; } if(u == v) return res - 2 * dp[v]; for(int i = __lg(depth[v]); i >= 0; i--){ if(parent[i][v] != parent[i][u]){ v = parent[i][v]; u = parent[i][u]; } } v = parent[0][v]; return res - 2 * dp[v]; } }; int main(){ ios::sync_with_stdio(false); cin.tie(0); int N, Q; ll X; cin >> N >> X >> Q; problem_H uf(N); int type, u, v, w; while(Q--){ cin >> type; if(type == 1){ cin >> v >> w; uf.merge(v, X, w); }else if(type == 2){ cin >> u >> v; ll d = uf.dist(u, v); cout << d << '\n'; if(d != -1) (X += d) %= N; }else if(type == 3){ cin >> v; cout << uf.diameter[uf.leader(v)] << '\n'; }else{ cin >> v; X += v; if(X >= N) X -= N; } } }