#include<bits/stdc++.h>
#pragma GCC optimize("O2")
#define deb(x) cout << #x << " = " << x <<endl
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define all(c) c.begin(), c.end()
#define endl "\n"
#define sz(u) (int)(u.size())
#define L(x)(2*x)
#define R(x)(2*x+1)
#define M(x,y)((x+y)/2)
typedef long long ll;
typedef unsigned long long ull;
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;
}
*/
