#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1;
vector<vector<int>> parent(N,vector<int>(21,0));
vector<char> letter(N);
vector<int> depth(N,0);
int cur=0;
void Init(){
letter[0]='.';
}
void TypeLetter(char c){
cur++;
depth[cur]=depth[cur-1]+1;
parent[cur][0]=cur-1;
letter[cur]=c;
for(int i=1;i<21;i++)
parent[cur][i]=parent[parent[cur][i-1]][i-1];
}
void UndoCommands(int u){
int nw=cur+1;
depth[nw]=depth[cur-u];
letter[nw]=letter[cur-u];
for(int i=0;i<21;i++)
parent[nw][i]=parent[cur-u][i];
cur++;
}
char GetLetter(int pos){
pos++;
//find kth parent of cur st k=depth[cur]-pos
int k=depth[cur]-pos;
if(k==0)
return letter[cur];
int cp=cur;
for(int i=20;i>=0;i--)
if((1<<i)&k)
cp=parent[cp][i];
return letter[cp];
}
/*
int main(){
Init();
TypeLetter('a');
TypeLetter('b');
cout<<GetLetter(1)<<endl;
TypeLetter('d');
UndoCommands(2);
UndoCommands(1);
cout<<GetLetter(2)<<endl;
TypeLetter('e');
UndoCommands(1);
UndoCommands(5);
TypeLetter('c');
cout<<GetLetter(2)<<endl;
UndoCommands(2);
cout<<GetLetter(2)<<endl;
}
*/
