///In the name of GOD
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const ll MXN = 2e5 + 10;
const ll LOG = 30;
const ll MXM = MXN * LOG + 10;
const ll INF = 1e8;
ll cntr;
int L[MXM], R[MXM], mtm[MXM];
void Pak(ll u = 1, ll bit = LOG - 1){
mtm[u] = INF;
if(L[u]) Pak(L[u], bit - 1), L[u] = 0;
if(R[u]) Pak(R[u], bit - 1), R[u] = 0;
}
void Add(ll val, ll tm, ll u = 1, ll bit = LOG - 1){
mtm[u] = min(mtm[u], tm);
if(bit == -1) return;
if((val >> bit) & 1LL){
if(!R[u]) R[u] = cntr ++;
Add(val, tm, R[u], bit - 1);
}
else{
if(!L[u]) L[u] = cntr ++;
Add(val, tm, L[u], bit - 1);
}
}
ll GetMax(ll val, ll tm, ll u = 1, ll bit = LOG - 1){
if(bit == -1) return 0;
if((val >> bit) & 1LL){
if(L[u] && mtm[L[u]] <= tm) return GetMax(val, tm, L[u], bit - 1) + (1LL << bit);
return GetMax(val, tm, R[u], bit - 1);
}
else{
if(R[u] && mtm[R[u]] <= tm) return GetMax(val, tm, R[u], bit - 1) + (1LL << bit);
return GetMax(val, tm, L[u], bit - 1);
}
}
ll n = 1, q, x, y;
ll px[MXN], ANS[MXN];
ll sub[MXN], big[MXN];
vector<pll> adj[MXN];
vector<pair<pll, ll>> Qry, Q[MXN];
string s;
void prep(ll u, ll par){
sub[u] = 1;
for(auto Pr : adj[u]){
ll v, w; tie(v, w) = Pr;
if(v != par){
px[v] = px[u] ^ w;
prep(v, u);
if(sub[v] > sub[big[u]]) big[u] = v;
sub[u] += sub[v];
}
}
}
void dfs(ll u, ll par){
Add(px[u], u);
for(auto Pr : adj[u]){
ll v = Pr.first;
if(v != par) dfs(v, u);
}
}
void DFS(ll u, ll par){
for(auto Pr : adj[u]){
ll v = Pr.first;
if(v == par || v == big[u]) continue;
DFS(v, u);
Pak();
}
if(big[u]) DFS(big[u], u);
for(auto Pr : adj[u]){
ll v = Pr.first;
if(v == par || v == big[u]) continue;
dfs(v, u);
}
Add(px[u], u);
for(auto Prr : Q[u]){
ll val, tm, id = Prr.second;
tie(val, tm) = Prr.first;
ANS[id] = GetMax(val, tm);
}
}
int main(){
ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
cntr = 2;
for(int i = 0; i < MXM; i ++) mtm[i] = INF;
cin >> q;
for(int i = 1; i <= q; i ++){
cin >> s >> x >> y;
if(s[0] == 'A'){
++ n;
adj[x].push_back({n, y});
adj[n].push_back({x, y});
}
else Qry.push_back({{x, y}, n});
}
prep(1, 0);
for(int i = 0; i < int(Qry.size()); i ++){
ll a, b, t = Qry[i].second; tie(a, b) = Qry[i].first;
Q[b].push_back({{px[a], t}, i});
}
DFS(1, 0);
for(int i = 0; i < int(Qry.size()); i ++) cout << ANS[i] << '\n';
return 0;
}
/*!
HE'S AN INSTIGATOR,
ENEMY ELIMINATOR,
AND WHEN HE KNOCKS YOU BETTER
YOU BETTER LET HIM IN.
*/
//! N.N
Compilation message
klasika.cpp: In function 'void Add(ll, ll, ll, ll)':
klasika.cpp:20:28: error: no matching function for call to 'min(int&, ll&)'
20 | mtm[u] = min(mtm[u], tm);
| ^
In file included from /usr/include/c++/9/bits/char_traits.h:39,
from /usr/include/c++/9/ios:40,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from klasika.cpp:3:
/usr/include/c++/9/bits/stl_algobase.h:198:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
198 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/9/bits/stl_algobase.h:198:5: note: template argument deduction/substitution failed:
klasika.cpp:20:28: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
20 | mtm[u] = min(mtm[u], tm);
| ^
In file included from /usr/include/c++/9/bits/char_traits.h:39,
from /usr/include/c++/9/ios:40,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from klasika.cpp:3:
/usr/include/c++/9/bits/stl_algobase.h:246:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
246 | min(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/9/bits/stl_algobase.h:246:5: note: template argument deduction/substitution failed:
klasika.cpp:20:28: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
20 | mtm[u] = min(mtm[u], tm);
| ^
In file included from /usr/include/c++/9/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
from klasika.cpp:3:
/usr/include/c++/9/bits/stl_algo.h:3444:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
3444 | min(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/9/bits/stl_algo.h:3444:5: note: template argument deduction/substitution failed:
klasika.cpp:20:28: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
20 | mtm[u] = min(mtm[u], tm);
| ^
In file included from /usr/include/c++/9/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
from klasika.cpp:3:
/usr/include/c++/9/bits/stl_algo.h:3450:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
3450 | min(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/9/bits/stl_algo.h:3450:5: note: template argument deduction/substitution failed:
klasika.cpp:20:28: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
20 | mtm[u] = min(mtm[u], tm);
| ^
