#include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // #include <ext/rope> using namespace std; // using namespace __gnu_pbds; typedef long long ll; typedef unsigned long long ull; typedef unsigned int uint; typedef long double ld; template <class T> using VV = vector<vector<T>>; using VI = vector<int>; using VVI = vector<vector<int>>; using VL = vector<long long>; using VVL = vector<vector<long long>>; using VC = vector<char>; using VVC = vector<vector<char>>; using VB = vector<bool>; using VVB = vector<vector<bool>>; using VD = vector<double>; using VVD = vector<vector<double>>; using PII = pair<int, int>; using PLL = pair<long long, long long>; using PIL = pair<int, long long>; using PLI = pair<long long, int>; using VPII = vector<pair<int, int>>; using VPLL = vector<pair<long long, long long>>; #define LINE '\n' #define SPACE ' ' #define PB push_back #define FOR(i, a, b) for (int i = (a); i < (int(b)); i++) #define FORE(i, a, b) for (int i = (a); i <= (int)((b)); i++) #define ALL(x) x.begin(), x.end() #define RALL(x) x.rbegin(), x.rend() #define sq(a) ((a) * (a)) #define sz(x) ((int)x.size()) #define fastio() \ ios_base::sync_with_stdio(false); \ cin.tie(nullptr); \ cout.tie(nullptr) #define debug(x) cerr << #x << " = " << x << endl; const ll MOD = 1e9 + 7; template <class T> inline void maxi(T &a, T b) { a = max(a, b); } template <class T> inline void mini(T &a, T b) { a = min(a, b); } template <class T> inline void addi(T &a, T b) { a = (a + b) % MOD; } template <class T> inline void subi(T &a, T b) { a = (a - b + MOD) % MOD; } template <class T> inline T add(T a, T b) { return (a + b) % MOD; } template <class T> inline T sub(T a, T b) { return (a - b + MOD) % MOD; } template <class T> inline T mul(T a, T b) { return ((a % MOD) * (b % MOD)) % MOD; } constexpr ll binpow(ll a, ll b, ll mod) { ll res = 1; while (b > 0) { if (b & 1) { res = (res * a) % mod; } a = (a * a) % mod; b >>= 1; } return res; } const int INF = 1e9; static const int MAX_N = 2e5 + 3; struct Trie { const static int MAX_W = MAX_N * 31; array<array<int, 2>, MAX_W> next; array<int, MAX_W> time; int triesz = 0; Trie() { fill(next.begin(), next.end(), array<int, 2>{-1, -1}); fill(time.begin(), time.end(), INF); } void clear() { fill(next.begin(), next.begin() + triesz + 1, array<int, 2>{-1, -1}); fill(time.begin(), time.begin() + triesz + 1, INF); triesz = 0; } void add(int x, int t) { int node = 0; mini(time[0], t); for (int i = 30; i >= 0; i--) { int bit = (x >> i) & 1; int v = next[node][bit]; if (v == -1) { v = ++triesz; next[node][bit] = v; } mini(time[v], t); node = v; } } // return maximal x ^ v, v in trie int get(int x, int t) { int node = 0; int cur = 0; for (int i = 30; i >= 0; i--) { int bit = (x >> i) & 1; int b1 = next[node][bit ^ 1]; int b2 = next[node][bit]; int nxt = -1; if (b1 != -1 && time[b1] <= t) { cur |= (1 << i); nxt = b1; } else if (b2 != -1 && time[b2] <= t) { nxt = b2; } assert(nxt != -1); node = nxt; } return cur; } }; VPII g[MAX_N]; VI app(MAX_N); VV<PII> queries(MAX_N); VI ans(MAX_N, -1); VI pref(MAX_N), stsz(MAX_N), heavy(MAX_N); void dfs(int c) { stsz[c] = 1; heavy[c] = -1; for (auto [v, edge] : g[c]) { pref[v] = pref[c] ^ edge; dfs(v); stsz[c] += stsz[v]; if (heavy[c] == -1 || stsz[heavy[c]] < stsz[v]) { heavy[c] = v; } } } Trie trie; void calc(int c); void add(int c) { trie.add(pref[c], app[c]); for (auto [v, edge] : g[c]) { add(v); } } void calc(int c) { for (auto [v, edge] : g[c]) { if (v == heavy[c]) continue; trie.clear(); calc(v); trie.clear(); } if (heavy[c] != -1) { calc(heavy[c]); } for (auto [v, edge] : g[c]) { if (v == heavy[c]) continue; add(v); } trie.add(pref[c], app[c]); for (auto [a, idx] : queries[c]) { int rt = trie.get(pref[a], idx); ans[idx] = rt; } } void solve() { int q; cin >> q; int n = 1; app[1] = 0; FOR(i, 0, q) { string type; int x, y; cin >> type >> x >> y; if (type == "Add") { g[x].PB({++n, y}); app[n] = i; } else { // x = a, y = b queries[y].PB({x, i}); } } dfs(1); calc(1); FOR(i, 0, q) { if (ans[i] != -1) { cout << ans[i] << LINE; } } } int main() { fastio(); int t = 1; // cin >> t; while (t--) solve(); }