/*
File created on 06/02/2021 at 18:42:44.
Link to problem: https://oj.uz/problem/view/COCI20_klasika
Description: use a trie structure, and to only consider subtree nodes use a disc/finish array;
Time complexity: O()
Space complexity: O()
Status: DEV
Copyright: Ⓒ 2021 Francois Vogel
*/
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <cstring>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
using namespace std;
#define mp pair<pii, int>
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ins insert
#define cls clear
#define ll long long
const int siz = 2e5;
const int MAX_P2 = 30;
vector<int> graph [siz];
int par [siz];
int xorTill [siz];
int disc [siz];
int rightMost [siz];
int tim = 0;
int dfs(int cn) {
disc[cn] = tim;
rightMost[cn] = tim;
tim++;
for (int nn : graph[cn]) rightMost[cn] = dfs(nn);
return rightMost[cn];
}
struct Node {
Node() {
lft = nullptr;
rgt = nullptr;
}
void add(int v, int k, int tins) {
if (k == MAX_P2) return;
int i = (v>>(MAX_P2-1-k))%2;
if (i == 0) {
if (lft == nullptr) lft = new Node();
zero.ins(tins);
lft->add(v, k+1, tins);
}
else {
if (rgt == nullptr) rgt = new Node();
one.ins(tins);
rgt->add(v, k+1, tins);
}
}
int get(int v, int k, int lb, int rb) {
if (k == MAX_P2) return 0;
//
int i = (v>>(MAX_P2-1-k))%2;
//
auto it1 = zero.upper_bound(lb-1);
bool lftFind = (it1 != zero.end() and (*it1) <= rb);
//
auto it2 = one.upper_bound(lb-1);
bool rgtFind = (it2 != one.end() and (*it2) <= rb);
//
if ((i == 0 and !rgtFind) or (i == 1 and lftFind)) {
return lft->get(v, k+1, lb, rb);
}
else {
return (1<<(MAX_P2-1-k))+rgt->get(v, k+1, lb, rb);
}
}
set<int> zero, one;
Node* lft, * rgt;
};
signed main() {
cin.tie(0);
// ios_base::sync_with_stdio(0);
int q;
cin >> q;
par[0] = -1;
xorTill[0] = 0;
int n = 1;
vector<pii> queries;
for (int i = 0; i < q; i++) {
string typ;
cin >> typ;
if (typ == "Add") {
int parentNode, edgeWeight;
cin >> parentNode >> edgeWeight;
// bitset<MAX_P2> bit(edgeWeight);
// bitset<MAX_P2> newBit;
// for (int i = 0; i < MAX_P2; i++) newBit[i] = bit[MAX_P2-i-1];
// edgeWeight = newBit.to_ulong();
parentNode--;
int curNode = n;
graph[parentNode].pb(curNode);
par[curNode] = parentNode;
xorTill[curNode] = xorTill[parentNode]^edgeWeight;
queries.pb(pii(curNode, -1));
n++;
}
else {
int a, b;
cin >> a >> b;
a--;
b--;
queries.pb(pii(a, b));
}
}
dfs(0);
Node* root = new Node();
root->add(0, 0, disc[0]);
for (pii i : queries) {
if (i.s == -1) {
root->add(xorTill[i.f], 0, disc[i.f]);
}
else {
int aNode = i.f;
int bNode = i.s;
int xorDefault = xorTill[aNode];
int xorMax = root->get(xorDefault, 0, disc[bNode], rightMost[bNode]);
cout << (xorDefault^xorMax) << endl;
}
}
int d = 0;
d++;
}
