#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"WAFFLES "<<i<<"<\n"
#define INF 1000000000000000000LL
#define EPS (0.00000000001L)
#define pi (3.141592653589793L)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007LL;
template<class A=pair<int, int> >
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i].ff << "," << a[i].ss <<" ";} cout<<endl;}
template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}}
vector<vector<ll> > anc;
vector<ll> dpth;
vector<pair<ll, char> > trie;
vector<ll> hist;
ll curr = -1;
ll addNode(ll pr, char c){
trie.pb({pr, c});
anc.pb({});
if(pr == -1){
dpth.pb(1);
return trie.size()-1;
}else{
dpth.pb(dpth[pr]+1);
}
anc.back().pb(pr);
ll mvup = pr;
ll n = 1;
while(1<<n < dpth.back()){
mvup = anc[mvup][n-1];
anc.back().pb(mvup);
n++;
}
return trie.size()-1;
}
ll upLift(ll cr, ll n){
ll bt = 0;
while(n > 0){
if(n & (1<<bt)){
cr = anc[cr][bt];
n -= (1<<bt);
}
bt++;
}
return cr;
}
void Init() {
}
void TypeLetter(char L) {
curr = addNode(curr, L);
hist.pb(curr);
}
void UndoCommands(int U) {
curr = hist[hist.size()-U-1];
}
char GetLetter(int P) {
return upLift(curr,dpth[curr]-P-1);
}
