#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#define nl "\n"
// --- Solver for the "Klasika" Problem (Correct Offline Approach) ---
// This solution is a clean, encapsulated implementation of the accepted algorithm.
// It works by processing queries offline, flattening the final tree with a DFS,
// and using a single Binary Trie where each node contains a std::set of DFS
// 'in' times to answer subtree queries efficiently.
class KlasikaSolver {
private:
static const int BITS = 30;
// The Trie structure, where each node holds a set of indices.
struct Trie {
struct Node {
Node* children[2];
std::set<int> ids;
Node() : children{nullptr, nullptr} {}
};
Node* root;
Trie() { root = new Node(); }
// Inserts the pre-calculated XOR sum for a given node `u`
// by adding its `in_time` to the sets along the path.
void insert(int in_time, int xor_sum) {
Node* curr = root;
for (int i = BITS - 1; i >= 0; --i) {
int bit = (xor_sum >> i) & 1;
if (!curr->children[bit]) {
curr->children[bit] = new Node();
}
curr = curr->children[bit];
curr->ids.insert(in_time);
}
}
// Finds the max XOR of `val` with any node in the subtree of `u`.
int query_max(int val, int in_u, int out_u) {
Node* curr = root;
int best_partner_xor = 0;
for (int i = BITS - 1; i >= 0; --i) {
int bit = (val >> i) & 1;
int required_bit = 1 - bit;
// Check if a valid partner exists down the desired path.
if (curr->children[required_bit]) {
auto& s = curr->children[required_bit]->ids;
auto it = s.lower_bound(in_u);
if (it != s.end() && *it <= out_u) {
// Found a partner in the subtree range. Take this path.
best_partner_xor |= (required_bit << i);
curr = curr->children[required_bit];
continue;
}
}
// Forced to take the other path.
best_partner_xor |= (bit << i);
curr = curr->children[bit];
}
return val ^ best_partner_xor;
}
};
struct Query {
int type; // 1 for Add, 2 for Query
int u, v;
};
std::vector<std::vector<std::pair<int, int>>> adj;
std::vector<int> dist, tin, tout;
int timer;
int node_count;
// DFS on the final tree to compute distances and in/out times.
void dfs_flattener(int u, int p, int current_xor_dist) {
tin[u] = ++timer;
dist[u] = current_xor_dist;
for (const auto& edge : adj[u]) {
int v = edge.first;
int w = edge.second;
if (v != p) {
dfs_flattener(v, u, current_xor_dist ^ w);
}
}
tout[u] = timer;
}
public:
void solve() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int q;
std::cin >> q;
std::vector<Query> queries(q);
adj.resize(q + 2);
node_count = 1;
// 1. Read all queries and build the final adjacency list.
for (int i = 0; i < q; ++i) {
std::string type;
std::cin >> type >> queries[i].u >> queries[i].v;
if (type == "Add") {
queries[i].type = 1;
node_count++;
adj[queries[i].u].push_back({node_count, queries[i].v});
} else {
queries[i].type = 2;
}
}
// 2. Perform one DFS on the final tree.
dist.resize(node_count + 1);
tin.resize(node_count + 1);
tout.resize(node_count + 1);
timer = 0;
dfs_flattener(1, 0, 0);
// 3. Process queries chronologically, inserting into the Trie as we go.
Trie trie;
int current_nodes_added = 1;
trie.insert(tin[1], dist[1]);
for (const auto& query : queries) {
if (query.type == 1) { // Add
current_nodes_added++;
trie.insert(tin[current_nodes_added], dist[current_nodes_added]);
} else { // Query
int a = query.u;
int b = query.v;
std::cout << trie.query_max(dist[a], tin[b], tout[b]) << nl;
}
}
}
};
int main() {
KlasikaSolver solver;
solver.solve();
return 0;
}
