#include <bits/stdc++.h>
using namespace std;
const int MAX = 2e6 + 15;
const int ALP = 30;
int trie[MAX][ALP], pai[MAX], cur, node;
char letter[MAX];
vector<int> states;
void Init() {}
void TypeLetter(char L) {
int id = L - 'a';
if(trie[cur][id] == 0){
trie[cur][id] = ++node;
pai[node] = cur;
}
cur = trie[cur][id];
letter[cur] = L;
states.emplace_back(cur);
}
void UndoCommands(int U) {
while(U-- && states.size())
states.pop_back();
cur = states.back();
states.emplace_back(cur);
}
char GetLetter(int P) {
int aux = cur;
string resp = "";
while(aux != 0){
resp += letter[aux];
aux = pai[aux];
}
return resp[P];
}
/*int main(){
int q; cin >> q;
while(q--){
int op; cin >> op;
if(op == 1){
char c; cin >> c;
TypeLetter(c);
}else if(op == 2){
int t; cin >> t;
UndoCommands(t);
}else{
int t; cin >> t;
cout << GetLetter(t) << '\n';
}
}
}*/
