#include #include #include using namespace std; const int maxn = 202020; typedef pair pii; const pii inf = make_pair(1<<30,0); char q; pii a[1<<20]; bool killed[maxn]; vector e[maxn]; int pos[maxn<<1], parent[maxn], n, m, t, i, N, v, u; void dfs(int v, int lvl, int pr) { a[++m] = make_pair(lvl,v); pos[v] = m; parent[v] = pr; for (int i = 0; i < e[v].size(); i++) { int u = e[v][i]; dfs(u, lvl + 1, v); a[++m] = make_pair(lvl,v); } } int lca(int u, int v) { int l = pos[u]; int r = pos[v]; if (l > r) swap(l, r); pii ans = inf; while (l <= r) { ans = min(ans, a[l]); ans = min(ans, a[r]); l = (l + 1) >> 1; r = (r - 1) >> 1; } return ans.second; } int get_pr(int v) { if (!killed[v]) return v; return parent[v] = get_pr(parent[v]); } int main() { freopen("mafia.in", "r", stdin); scanf("%d\n", &m); n = 1; while (m--) { q = getchar(); if (q == '+') { scanf("%d\n", &v); e[v].push_back(++n); } else if (q == '-') scanf("%d\n", &v); else scanf("%d%d\n", &u, &v); } N = n+n-1; t = 1; while (t < N) t <<= 1; m = t-1; dfs(1,1,0); for (i = t+N; i < t+t; i++) a[i] = inf; for (i = t-1; i > 0; i--) a[i] = min(a[i<<1],a[(i<<1)+1]); freopen("mafia.in", "r", stdin); freopen("mafia.out", "w", stdout); scanf("%d\n", &m); while (m--) { q = getchar(); if (q == '+') scanf("%d\n", &v); else if (q == '-') { scanf("%d\n", &v); killed[v] = 1; } else { scanf("%d%d\n", &u, &v); printf("%d\n", get_pr(lca(u, v))); } } //exit(0); return 0; }