#include <bits/stdc++.h>
using namespace std;
const int MAXB = 31; // bits are 0 … 29
const int THRESH = 2000; // nodes with range > THRESH use a trie
// global pool for all trie nodes (each node has two child indices)
vector<array<int, 2>> trie_nodes;
// insert value into the trie rooted at 'root' (root is modified)
void insert(int &root, int val) {
if (root == 0) {
root = trie_nodes.size();
trie_nodes.push_back({0, 0});
}
int node = root;
for (int i = MAXB - 1; i >= 0; --i) {
int b = (val >> i) & 1;
if (b == 0) {
if (trie_nodes[node][0] == 0) {
trie_nodes[node][0] = trie_nodes.size();
trie_nodes.push_back({0, 0});
}
node = trie_nodes[node][0];
} else {
if (trie_nodes[node][1] == 0) {
trie_nodes[node][1] = trie_nodes.size();
trie_nodes.push_back({0, 0});
}
node = trie_nodes[node][1];
}
}
}
// maximum xor of x with any value in the trie rooted at 'root'
int query_trie(int root, int x) {
if (root == 0) return 0;
int node = root;
int ans = 0;
for (int i = MAXB - 1; i >= 0; --i) {
int b = (x >> i) & 1;
if (b == 0) {
if (trie_nodes[node][1]) {
ans |= (1 << i);
node = trie_nodes[node][1];
} else {
node = trie_nodes[node][0];
}
} else {
if (trie_nodes[node][0]) {
ans |= (1 << i);
node = trie_nodes[node][0];
} else {
node = trie_nodes[node][1];
}
}
}
return ans;
}
struct Operation {
int type; // 0 = Add, 1 = Query
int a, b; // for Query: a, b
int node; // for Add: new node number
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int Q;
cin >> Q;
vector<Operation> ops(Q);
int nodeCount = 1; // node 1 already exists
vector<int> parent(Q + 5), weight(Q + 5);
parent[1] = 0;
for (int i = 0; i < Q; ++i) {
string s;
cin >> s;
if (s == "Add") {
int x, y;
cin >> x >> y;
++nodeCount;
parent[nodeCount] = x;
weight[nodeCount] = y;
ops[i] = {0, 0, 0, nodeCount};
} else { // Query
int a, b;
cin >> a >> b;
ops[i] = {1, a, b, 0};
}
}
int N = nodeCount; // total number of nodes
// compute xor from root to each node (node numbers are in creation order)
vector<int> d(N + 1);
d[1] = 0;
for (int i = 2; i <= N; ++i) {
d[i] = d[parent[i]] ^ weight[i];
}
// build adjacency list for DFS
vector<vector<int>> adj(N + 1);
for (int i = 2; i <= N; ++i) {
adj[parent[i]].push_back(i);
}
// Euler tour (preorder) – compute in[u] and out[u]
vector<int> in(N + 1), out(N + 1);
int timer = 0;
stack<pair<int, int>> st; // (node, state) 0 = enter, 1 = exit
st.push({1, 0});
while (!st.empty()) {
auto [u, state] = st.top();
st.pop();
if (state == 0) {
in[u] = ++timer;
st.push({u, 1});
// push children (order does not matter for correctness)
for (int v : adj[u]) {
st.push({v, 0});
}
} else {
out[u] = timer;
}
}
// segment tree data
vector<int> seg_root(4 * N + 5, 0); // trie roots for large nodes
vector<vector<int>> seg_vec(4 * N + 5); // value lists for small nodes
// recursive update
function<void(int, int, int, int, int)> update =
[&](int node, int l, int r, int pos, int val) {
int len = r - l + 1;
if (len > THRESH) {
insert(seg_root[node], val);
} else {
seg_vec[node].push_back(val);
}
if (l == r) return;
int mid = (l + r) / 2;
if (pos <= mid) update(node * 2, l, mid, pos, val);
else update(node * 2 + 1, mid + 1, r, pos, val);
};
// recursive range query
function<int(int, int, int, int, int, int)> query_range =
[&](int node, int l, int r, int ql, int qr, int x) -> int {
if (ql <= l && r <= qr) {
int len = r - l + 1;
if (len > THRESH) {
return query_trie(seg_root[node], x);
} else {
int best = 0;
for (int v : seg_vec[node]) {
best = max(best, x ^ v);
}
return best;
}
}
int mid = (l + r) / 2;
int res = 0;
if (ql <= mid) res = max(res, query_range(node * 2, l, mid, ql, qr, x));
if (qr > mid) res = max(res, query_range(node * 2 + 1, mid + 1, r, ql, qr, x));
return res;
};
// initially node 1 exists
update(1, 1, N, in[1], d[1]);
// process all operations in order
for (const auto &op : ops) {
if (op.type == 0) { // Add
int v = op.node;
update(1, 1, N, in[v], d[v]);
} else { // Query
int a = op.a, b = op.b;
int ans = query_range(1, 1, N, in[b], out[b], d[a]);
cout << ans << '\n';
}
}
return 0;
}
