#include <iostream>
#include <vector>
#include <string>
#include <iomanip>
#include <queue>
#include <cmath>
#include <algorithm>
#include <unordered_map>
#include <tuple>
#include <iomanip>
#include <stdio.h>
#include <map>
#include <bitset>
#include <set>
#include <stack>
#include <queue>
#include <unordered_set>
#include <cassert>
#include <stdlib.h>
#include <time.h>
#include <random>


//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,sse3,sse4")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("fast-math")
//#pragma GCC target("avx2")
//#pragma GCC optimize("section-anchors")
//#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
//#pragma GCC optimize("vpt")
//#pragma GCC optimize("rename-registers")
//#pragma GCC optimize("move-loop-invariants")
//#pragma GCC optimize("unswitch-loops")
//#pragma GCC optimize("function-sections")
//#pragma GCC optimize("data-sections")

//#define int long long
#define ll long long
#define ull unsigned long long
#define all(a) (a).begin(), (a).end()
#define pii pair<int, int>
#define pb push_back
#define ld long double

using namespace std;

//const int INF = 1e17;
//const int mod = 2600000069;
//const int p = 179;
const int MAXN = 2e5 + 1;
const int logn = 19;

int up[MAXN][logn], f[MAXN], tin[MAXN], tout[MAXN], par[MAXN], nxt[MAXN];
vector<int> g[MAXN];
int ind = 1, timer = 0;

struct event {
    int t, u, v;
    event(int u_) {
        t = 0;
        u = u_;
    }
    event(int u_, int v_) {
        t = 1;
        u = u_;
        v = v_;
    }
};

vector<event> c;

void dfs(int v, int p) {
    tin[v] = timer++;
    up[v][0] = p;
    par[v] = p;
    nxt[v] = v;
    for (int i = 1; i < logn; i++) up[v][i] = up[up[v][i - 1]][i - 1];
    for (auto k : g[v]) {
        if (k != p) dfs(k, v);
    }
    tout[v] = timer;
}

bool ancestor(int v, int u) { // v -> u
    return tin[v] <= tin[u] && tout[v] >= tout[u];
}

int get_par(int v) {
    if (nxt[v] == v) return v;
    return nxt[v] = get_par(nxt[v]);
}

int lca(int v, int u) {
    if (ancestor(u, v)) return u;
    if (ancestor(v, u)) return v;
    for (int i = logn - 1; i >= 0; i--) {
        if (!ancestor(up[v][i], u)) {
            v = up[v][i];
        }
    }
    v = up[v][0];
//    cout <<"v: " <<  v << "\n";
    if (f[v]) return get_par(v);
    return v;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    for (int i = 0; i < logn; i++) {
        up[0][i] = 0;
    }
    nxt[0] = 0;
    int n;
    cin >> n;
    int u, v;
    char t;
    for (int i = 0; i < n; i++) {
        cin >> t;
        if (t == '+') {
            cin >> v;
            v--;
            g[ind].pb(v);
            g[v].pb(ind);
            ind++;
        } else if (t == '-') {
            cin >> v;
            v--;
            c.pb(event(v));
        } else {
            cin >> v >> u;
            v--;u--;
            c.pb(event(u, v));
        }
    }
    dfs(0, 0);
    for (auto k : c) {
        if (k.t) {
            cout << lca(k.u, k.v) + 1 << "\n";
        } else {
            f[k.u] = 1;
            nxt[k.u] = par[k.u];
        }
    }
}
/*
11
+ 1
+ 1
+ 2
? 2 3
? 1 3
? 2 4
+ 4
+ 4
- 4
? 5 6
? 5 5
-> 1 1 2 2 5
*/