#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
const int LOG_VAL = 30;
struct QueryInfo {
int id; // ID của truy vấn (để in ra đúng thứ tự)
int type; // 0: Add, 1: Query
int u; // Add: node index, Query: start node a
int v; // Add: weight, Query: subtree node b
int time_added; // Add: thời điểm thêm (node ID)
};
int n = 1, q;
vector<pair<int, int>> adj[MAXN];
int st[MAXN], en[MAXN], D[MAXN]; // D[u] là XOR path từ root đến u
int timer;
int ans[MAXN]; // Lưu kết quả truy vấn
vector<QueryInfo> queries;
// DFS để linearize cây (Euler tour) và tính XOR path
void dfs(int u, int p) {
st[u] = ++timer;
for (auto &edge : adj[u]) {
int v = edge.first;
int w = edge.second;
if (v != p) {
D[v] = D[u] ^ w;
dfs(v, u);
}
}
en[u] = timer;
}
struct Node {
Node *child[2];
int cnt;
Node() { child[0] = child[1] = NULL; cnt = 0; }
};
Node* null;
void init_trie() {
null = new Node();
null->child[0] = null->child[1] = null;
null->cnt = 0;
}
void insert(Node* prev, Node* &curr, int val)
{
curr = new Node();
*curr = *prev;
curr->cnt++;
Node* p = curr;
for (int i = LOG_VAL; i >= 0; i--)
{
int bit = (val >> i) & 1;
p->child[bit] = new Node();
*p->child[bit] = *prev->child[bit];
p->child[bit]->cnt++;
p = p->child[bit];
prev = prev->child[bit];
}
}
int query(Node* verL, Node* verR, int val)
{
int res = 0;
for (int i = LOG_VAL; i >= 0; i--)
{
int bit = (val >> i) & 1;
int want = 1 - bit;
if (verR->child[want]->cnt - verL->child[want]->cnt > 0)
{
res += (1 << i);
verR = verR->child[want];
verL = verL->child[want];
}
else
{
verR = verR->child[bit];
verL = verL->child[bit];
}
}
return res;
}
Node* roots[MAXN];
void solve_cdq(int l, int r, vector<int>& q_indices)
{
if (q_indices.empty())
return;
if (l == r)
return;
int mid = (l + r) >> 1;
vector<int> left_q, right_q;
for (int id : q_indices)
{
if (queries[id].id <= mid)
left_q.push_back(id);
else
right_q.push_back(id);
}
solve_cdq(l, mid, left_q);
solve_cdq(mid + 1, r, right_q);
vector<pair<int, int>> nodes_to_add;
for (int id : left_q) {
if (queries[id].type == 0)
{
int u = queries[id].time_added;
nodes_to_add.push_back({st[u], D[u]});
}
}
if (l == 1)
nodes_to_add.push_back({st[1], D[1]});
sort(nodes_to_add.begin(), nodes_to_add.end());
vector<Node*> versions;
vector<int> version_st;
Node* current_root = null;
versions.push_back(null);
version_st.push_back(0);
for (auto p : nodes_to_add)
{
int pos = p.first;
int val = p.second;
Node* new_root;
insert(current_root, new_root, val);
current_root = new_root;
versions.push_back(current_root);
version_st.push_back(pos);
}
for (int id : right_q)
{
if (queries[id].type == 1)
{
int u = queries[id].u;
int b = queries[id].v;
auto itR = upper_bound(version_st.begin(), version_st.end(), en[b]);
int idxR = prev(itR) - version_st.begin();
auto itL = upper_bound(version_st.begin(), version_st.end(), st[b] - 1);
int idxL = prev(itL) - version_st.begin();
int val = query(versions[idxL], versions[idxR], D[u]);
ans[id] = max(ans[id], val);
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
init_trie();
cin >> q;
int node_cnt = 1;
queries.resize(q + 1);
for (int i = 1; i <= q; i++)
{
string type;
int u, v;
cin >> type >> u >> v;
queries[i].id = i;
if (type == "Add")
{
queries[i].type = 0;
queries[i].u = u;
queries[i].v = v;
node_cnt++;
queries[i].time_added = node_cnt;
adj[u].push_back({node_cnt, v});
adj[node_cnt].push_back({u, v});
}
else
{
queries[i].type = 1;
queries[i].u = u;
queries[i].v = v;
ans[i] = 0;
}
}
D[1] = 0;
dfs(1, 0);
vector<int> q_indices;
for(int i = 1; i <= q; i++)
q_indices.push_back(i);
solve_cdq(1, q, q_indices);
for (int i = 1; i <= q; i++)
if (queries[i].type == 1)
cout << ans[i] << "\n";
return 0;
}
