#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#define nl "\n"
// --- Data Structures for Offline Solution ---
const int BITS = 30;
// Standard, non-persistent Binary Trie for Max XOR queries on a set of numbers.
struct BinaryTrie {
struct Node {
Node* children[2];
int count;
Node() : count(0), children{nullptr, nullptr} {}
};
Node* root;
BinaryTrie() { root = new Node(); }
void insert(int val) {
Node* curr = root;
for (int i = BITS - 1; i >= 0; --i) {
curr->count++;
int bit = (val >> i) & 1;
if (!curr->children[bit]) {
curr->children[bit] = new Node();
}
curr = curr->children[bit];
}
curr->count++;
}
int get_max_xor(int val) {
Node* curr = root;
int max_xor_val = 0;
for (int i = BITS - 1; i >= 0; --i) {
int bit = (val >> i) & 1;
int required_bit = 1 - bit;
if (curr->children[required_bit] && curr->children[required_bit]->count > 0) {
max_xor_val |= (1 << i);
curr = curr->children[required_bit];
} else {
curr = curr->children[bit];
}
}
return max_xor_val;
}
};
// A Segment Tree where each node contains a Binary Trie.
// This allows for range queries that perform an operation (max_xor) on the aggregated data.
struct SegTreeNode {
BinaryTrie trie;
};
std::vector<SegTreeNode> seg_tree;
int N_final; // Final number of nodes in the tree
void seg_tree_update(int node, int start, int end, int idx, int val) {
if (start == end) {
seg_tree[node].trie.insert(val);
return;
}
seg_tree[node].trie.insert(val);
int mid = start + (end - start) / 2;
if (start <= idx && idx <= mid) {
seg_tree_update(2 * node, start, mid, idx, val);
} else {
seg_tree_update(2 * node + 1, mid + 1, end, idx, val);
}
}
int seg_tree_query(int node, int start, int end, int l, int r, int val) {
if (r < start || end < l) {
return 0;
}
if (l <= start && end <= r) {
return seg_tree[node].trie.get_max_xor(val);
}
int mid = start + (end - start) / 2;
int p1 = seg_tree_query(2 * node, start, mid, l, r, val);
int p2 = seg_tree_query(2 * node + 1, mid + 1, end, l, r, val);
return std::max(p1, p2);
}
// --- Solver for the "Klasika" Problem (Offline Approach) ---
struct Query {
int type, time, id;
int u, v, w; // u,v for query, u,w for add
};
class KlasikaSolver {
private:
struct Edge {
int to;
int weight;
};
std::vector<std::vector<Edge>> adj;
std::vector<int> dist, tin, tout, dfs_order_pos, dfs_order_val;
int timer;
void dfs_flattener(int u, int p, int current_xor_dist) {
tin[u] = ++timer;
dfs_order_pos[u] = timer;
dfs_order_val[timer] = 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:
void solve() {
int q;
std::cin >> q;
std::vector<Query> queries(q);
int node_count = 1;
adj.resize(q + 2);
for (int i = 0; i < q; ++i) {
std::string type;
std::cin >> type;
queries[i].id = i;
if (type == "Add") {
queries[i].type = 1;
std::cin >> queries[i].u >> queries[i].w;
node_count++;
adj[queries[i].u].push_back({node_count, queries[i].w});
queries[i].time = node_count;
} else {
queries[i].type = 2;
std::cin >> queries[i].u >> queries[i].v;
queries[i].time = node_count;
}
}
N_final = node_count;
// Perform one DFS on the final tree
dist.resize(N_final + 1);
tin.resize(N_final + 1);
tout.resize(N_final + 1);
dfs_order_pos.resize(N_final + 1);
dfs_order_val.resize(N_final + 1);
timer = 0;
dfs_flattener(1, 0, 0);
// Sort queries by their 'time' (node_count when asked)
std::sort(queries.begin(), queries.end(), [](const Query& a, const Query& b) {
return a.time < b.time;
});
std::vector<int> answers(q);
seg_tree.resize(4 * N_final);
int current_nodes_in_struct = 0;
// Process queries and add nodes to the data structure chronologically
for (const auto& query : queries) {
while (current_nodes_in_struct < query.time) {
current_nodes_in_struct++;
seg_tree_update(1, 1, N_final, dfs_order_pos[current_nodes_in_struct], dist[current_nodes_in_struct]);
}
if (query.type == 2) {
int a = query.u;
int b = query.v;
int l = tin[b];
int r = tout[b];
answers[query.id] = seg_tree_query(1, 1, N_final, l, r, dist[a]);
}
}
for (int i = 0; i < q; ++i) {
if (answers[i] != 0 || (answers[i]==0 && queries[i].type==2)) { // Print only for query types
bool is_query = false;
for(const auto& qr : queries){
if(qr.id == i && qr.type == 2){
is_query = true;
break;
}
}
if(is_query) std::cout << answers[i] << nl;
}
}
}
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
KlasikaSolver solver;
solver.solve();
return 0;
}
