#include <bits/stdc++.h>
#define pb push_back
#define xx first
#define yy second
#define mp make_pair
using namespace std;
int curr;
vector<pair<char, int> > s; //storing chars and ranks
vector<int> node_par; //storing each node's origin
vector<int> par; //storing each cmd's origin
vector<int> pos; //storing each cmd's position in "s"
void Init() {
s.pb(mp('#', 0));
curr = 0; //current node is 0
pos.pb(0);
node_par.pb(0);
par.pb(0); //cmd zero came from zero lol
}
void TypeLetter(char L) {
par.pb(curr); // new cmd is came from current cmd :v
s.pb(mp(L, s[ pos[curr] ].yy + 1)); //typing letter means new node
node_par.pb(pos[curr]);
pos.pb(s.size() - 1);
curr++;
}
void UndoCommands(int U) {
int origin = curr;
for (int cnt = 1; cnt <= U; cnt++){
origin = par[origin];
}
par.pb(curr);
curr++;
pos.pb(pos[origin]);
}
char GetLetter(int P) {
P++;
int tmp = pos[curr];
while( s[tmp].yy > P ){
tmp = node_par[tmp];
}
return s[tmp].xx;
}
// int main(){ //driver-chan
// Init();
// TypeLetter('a');
// cout << GetLetter(0);
// TypeLetter('b');
// cout << GetLetter(0);
// cout << GetLetter(1);
// UndoCommands(1);
// cout << GetLetter(0);
// TypeLetter('c');
// cout << GetLetter(1);
// // for (auto c : s){
// // cout << c.yy ;
// // }
// // cout << s.xx;
// }
