#include <iostream>
#include <vector>
#include <algorithm>
#define nl "\n"
// --- Persistent Binary Trie (Clean Template) ---
// This is a clean, encapsulated C++ implementation based on the logic of the
// accepted competitive programming solution. It uses a pre-allocated node pool
// and integer indices instead of raw pointers to achieve high performance and
// avoid runtime errors.
class PersistentBinaryTrie {
private:
static const int BITS = 30; // For values up to 2^30
struct Node {
int children[2];
int count;
Node() : count(0) {
children[0] = children[1] = 0; // Index 0 is the sentinel null node.
}
};
std::vector<Node> node_pool;
std::vector<int> roots;
int node_idx;
int clone_node(int u) {
node_pool[node_idx] = node_pool[u];
return node_idx++;
}
int insert_internal(int root_idx, int val) {
int new_root = clone_node(root_idx);
node_pool[new_root].count++;
int curr_new = new_root;
int curr_old = root_idx;
for (int i = BITS - 1; i >= 0; --i) {
int bit = (val >> i) & 1;
int old_child_idx = node_pool[curr_old].children[bit];
int new_child_idx = clone_node(old_child_idx);
node_pool[curr_new].children[bit] = new_child_idx;
node_pool[new_child_idx].count++;
curr_new = new_child_idx;
curr_old = old_child_idx;
}
return new_root;
}
int query_max_xor(int l_root_idx, int r_root_idx, int x) {
int y = 0;
for (int i = BITS - 1; i >= 0; --i) {
int bit = (x >> i) & 1;
int required_bit = 1 - bit;
int r_child_idx = node_pool[r_root_idx].children[required_bit];
int l_child_idx = node_pool[l_root_idx].children[required_bit];
if (node_pool[r_child_idx].count > node_pool[l_child_idx].count) {
y |= (required_bit << i);
r_root_idx = r_child_idx;
l_root_idx = l_child_idx;
} else {
y |= (bit << i);
r_root_idx = node_pool[r_root_idx].children[bit];
l_root_idx = node_pool[l_root_idx].children[bit];
}
}
return y;
}
public:
PersistentBinaryTrie(int max_nodes) {
node_pool.resize(max_nodes * (BITS + 2));
node_idx = 1;
roots.reserve(max_nodes + 1);
roots.push_back(0);
}
void add(int x) {
roots.push_back(insert_internal(roots.back(), x));
}
int get_max_xor(int l, int r, int x) {
// Note: The PBT works on a 0-indexed array, but the problem uses 1-based ranges.
// The calling context must handle this conversion.
return query_max_xor(roots[l - 1], roots[r], x);
}
};
// --- Solver for the "Klasika" Problem ---
class KlasikaSolver {
private:
struct Edge {
int to;
int weight;
};
int node_count;
std::vector<std::vector<Edge>> adj;
std::vector<int> dist; // XOR sum from root 1 to node i
// For mapping tree to 1D array
std::vector<int> tin, tout, dfs_order;
int timer;
void dfs_flattener(int u, int p, int current_xor_dist) {
tin[u] = ++timer;
dfs_order[timer] = u;
dist[u] = current_xor_dist;
for (const auto& edge : adj[u]) {
int v = edge.to;
if (v != p) {
dfs_flattener(v, u, current_xor_dist ^ edge.weight);
}
}
tout[u] = timer;
}
public:
KlasikaSolver(int max_q) {
node_count = 1;
adj.resize(max_q + 2);
dist.resize(max_q + 2);
tin.resize(max_q + 2);
tout.resize(max_q + 2);
dfs_order.resize(max_q + 2);
dist[1] = 0;
}
void add_node(int parent, int weight) {
node_count++;
adj[parent].push_back({node_count, weight});
adj[node_count].push_back({parent, weight}); // Assuming undirected for dist calculation
}
int process_query(int a, int b) {
// 1. Flatten the current tree structure with a DFS
timer = 0;
dfs_flattener(1, 0, 0);
// 2. Build a temporary PBT on the DFS-ordered distances
PersistentBinaryTrie pbt(node_count);
for (int i = 1; i <= node_count; ++i) {
int node_id = dfs_order[i];
pbt.add(dist[node_id]);
}
// 3. The subtree of `b` is now the range [tin[b], tout[b]]
int l = tin[b];
int r = tout[b];
int val_a = dist[a];
// 4. Query the PBT for the best partner and return the max XOR value
int best_partner = pbt.get_max_xor(l, r, val_a);
return val_a ^ best_partner;
}
};
void solve() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int q;
std::cin >> q;
KlasikaSolver solver(q);
for (int i = 0; i < q; ++i) {
std::string type;
std::cin >> type;
if (type == "Add") {
int x, y;
std::cin >> x >> y;
solver.add_node(x, y);
} else { // Query
int a, b;
std::cin >> a >> b;
std::cout << solver.process_query(a, b) << nl;
}
}
}
int main() {
solve();
return 0;
}
