#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define task "task"
const int ar = 2e5 + 5;
const ll mod = 1e9 + 7;
const int inf = 1e9;
int q, n = 1;
vector<int> ad[ar];
int d[ar], app[ar];
vector<pair<int, int>> Q[ar];
int sz[ar], timedfs = 0;
int in[ar];
int par[ar];
void dfs(int u)
{
sz[u] = 1;
for (int v : ad[u])
{
dfs(v);
par[v] = u;
sz[u] = sz[v] + 1;
}
}
int curchain = 1;
int head[ar], chainid[ar];
void hld(int u)
{
if (head[curchain] == 0)
{
head[curchain] = u;
}
in[u] = ++timedfs;
chainid[u] = curchain;
int _sz = 0;
int bigc = 0;
for (int v : ad[u])
{
if (sz[v] > _sz) _sz = sz[v], bigc = v;
}
if (bigc) hld(bigc);
for (int v : ad[u])
{
if (v == bigc) continue;
curchain++;
hld(v);
}
}
vector<pair<int, int>> on[ar], off[ar];
void get_segments(int u, int v)
{
int root = u;
while(u != 0)
{
int r = in[u];
int l = in[head[chainid[u]]];
on[l].push_back({v, app[root]});
off[r].push_back({v, app[root]});
u = par[head[chainid[u]]];
}
}
struct Trie
{
struct Node
{
int cnt;
int L, R;
int child[2];
} nodes[ar * 30];
multiset<int> ST[ar];
struct segment_tree
{
int st[(1 << 19) + 5];
void update(int u, int v)
{
int id = 1;
int l = 1;
int r = n;
while (l < r)
{
int mid = l + r >> 1;
if (mid >= u)
{
id <<= 1;
r = mid;
}
else
{
id = id << 1 | 1;
l = mid + 1;
}
}
st[id] = v;
while(id > 1)
{
id >>= 1;
st[id] = min(st[id << 1], st[id << 1 | 1]);
}
}
int get(int id, int l, int r, int u, int v)
{
if (u <= l && r <= v) return st[id];
int mid = l + r >> 1;
if (mid >= u)
{
if (mid + 1 <= v)
return min(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
return get(id << 1, l, mid, u, v);
}
return get(id << 1 | 1, mid + 1, r, u, v);
}
} st;
int cur = 0;
Trie()
{
nodes[0].child[0] = nodes[0].child[1] = -1;
nodes[0].cnt = 0;
nodes[0].L = inf;
nodes[0].R = -inf;
}
int new_node()
{
++cur;
nodes[cur].child[0] = nodes[cur].child[1] = -1;
nodes[cur].cnt = 0;
nodes[cur].L = inf;
nodes[cur].R = -inf;
return cur;
}
void build(int u)
{
int p = 0;
for (int i = 29; i >= 0; i--)
{
int c = (u >> i) & 1;
if (nodes[p].child[c] == -1) nodes[p].child[c] = new_node();
p = nodes[p].child[c];
}
}
int cnt = 0;
void dfs(int u)
{
bool ok = false;
if (nodes[u].child[0] != -1)
{
ok = true;
dfs(nodes[u].child[0]);
nodes[u].L = min(nodes[u].L, nodes[nodes[u].child[0]].L);
nodes[u].R = max(nodes[u].R, nodes[nodes[u].child[0]].R);
}
if (nodes[u].child[1] != -1)
{
ok = true;
dfs(nodes[u].child[1]);
nodes[u].L = min(nodes[u].L, nodes[nodes[u].child[1]].L);
nodes[u].R = max(nodes[u].R, nodes[nodes[u].child[1]].R);
}
if (!ok) nodes[u].L = nodes[u].R = ++cnt;
}
void add(int u, int v)
{
int p = 0;
for (int i = 29; i >= 0; i--)
{
int c = (u >> i) & 1;
p = nodes[p].child[c];
nodes[p].cnt++;
if (i == 0)
{
ST[nodes[p].L].insert(v);
int val = *ST[nodes[p].L].begin();
st.update(nodes[p].L, val);
}
}
}
void del(int u, int v)
{
int p = 0;
for (int i = 29; i >= 0; i--)
{
int c = (u >> i) & 1;
p = nodes[p].child[c];
nodes[p].cnt--;
if (i == 0)
{
ST[nodes[p].L].erase(ST[nodes[p].L].find(v));
int val = (ST[nodes[p].L].size()) ? (*ST[nodes[p].L].begin()) : inf;
st.update(nodes[p].L, val);
}
}
}
int get(int u, int v)
{
int ans = 0;
int p = 0;
for (int i = 29; i >= 0; i--)
{
int c = (u >> i) & 1;
if (nodes[p].child[c ^ 1] != -1 && nodes[nodes[p].child[c ^ 1]].cnt)
{
int val = st.get(1, 1, n, nodes[nodes[p].child[c ^ 1]].L, nodes[nodes[p].child[c ^ 1]].R);
if (val <= v)
{
ans += 1 << i;
p = nodes[p].child[c ^ 1];
}
else p = nodes[p].child[c];
}
else p = nodes[p].child[c];
}
return ans;
}
} trie;
int ord[ar];
int ans[ar];
bool isquery[ar];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if (fopen(task".inp", "r"))
{
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
cin >> q;
for (int i = 1; i <= q; i++)
{
string s;
int x, y;
cin >> s >> x >> y;
if (s == "Add")
{
ad[x].push_back(++n);
d[n] = d[x] ^ y;
app[n] = i;
}
else
{
isquery[i] = true;
Q[y].push_back({x, i});
}
}
dfs(1);
hld(1);
for (int i = 1; i <= n; i++)
{
get_segments(i, d[i]);
trie.build(d[i]);
ord[i] = i;
}
trie.dfs(0);
sort(ord + 1, ord + n + 1, [&](int x, int y)
{
return in[x] < in[y];
});
for (int i = 1; i <= n; i++)
{
int u = ord[i];
for (auto [v, t] : on[i]) trie.add(v, t);
for (auto [v, t] : Q[u]) ans[t] = trie.get(d[v], t);
for (auto [v, t] : off[i]) trie.del(v, t);
}
for (int i = 1; i <= q; i++)
{
if (isquery[i]) cout << ans[i] << '\n';
}
}
