#include using namespace std; using ll = long long; struct problem_H { int MAX_LOGV, N; vector>> G; vector> parent; vector dp; vector depth; vector log_table; vector parent_or_size; vector diameter; vector> diameter_vertex; queue que; problem_H(int n) : N(n), MAX_LOGV(__lg(n) + 1), parent(MAX_LOGV, vector(n, -1)), parent_or_size(n, -1), G(n), dp(n), depth(n), diameter(n), diameter_vertex(n), log_table(n) { array tmp{}; diameter_vertex[0] = tmp; tmp[0]++, tmp[1]++; diameter_vertex[0] = tmp; tmp[0]++, tmp[1]++; for(int i = 1; i + 1 < MAX_LOGV; i++){ int r = 1 << i + 1; for(int j = 1 << i; j < r; j++){ log_table[j] = i; diameter_vertex[j] = tmp; tmp[0]++, tmp[1]++; } } int logv = __lg(N); for(int i = tmp[0]; i < N; i++){ log_table[i] = logv; diameter_vertex[i] = tmp; tmp[0]++, tmp[1]++; } } 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(const int &v, const int &par, const int &w){ parent[0][v] = par; int depth_log = log_table[max(depth[v], depth[par] + 1)]; depth[v] = depth[par] + 1; dp[v] = dp[par] + w; 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(const int &x, const 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[log_table[d & -d]][v]; d -= d & -d; } if(u == v) return res - 2 * dp[v]; for(int i = log_table[depth[v]]; i >= 0; i--){ if(parent[i][v] != parent[i][u]){ v = parent[i][v]; u = parent[i][u]; } } return res - 2 * dp[parent[0][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; } } }