//# pragma GCC optimize("Ofast,no-stack-protector")
//# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//# pragma GCC optimize("Ofast")
//# pragma GCC optimization ("unroll-loops")
# include "bits/stdc++.h"
/*
# include <ext/pb_ds/tree_policy.hpp>
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/rope>
*/
std::pair<int,int> DR[] = {{-1,0},{0,1},{1,0},{0,-1},{-1,1},{-1,-1},{1,1},{1,-1}};
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define rcg(s) cout << s;exit(0)
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define all(s) s.begin(),s.end()
# define sz(x) (int)((x).size())
//# define int ll
using namespace std;
char val[1 << 20];
int p[1 << 20][20];
vector<int>vec;
int curr,k;
int dep[1 << 20];
int nxt[1 << 20][26];
void Init()
{
vec.pb(0);
}
void TypeLetter(char L)
{
if(!nxt[curr][L - 'a'])
{
nxt[curr][L - 'a'] = ++k;
dep[k] = dep[curr] + 1;
val[k] = L;
p[k][0] = curr;
for(int i = 1;i <= 20;i++)
{
p[k][i] = p[p[k][i - 1]][i - 1];
}
curr = k;
}
else curr = nxt[curr][L - 'a'];
vec.pb(curr);
}
void UndoCommands(int U)
{
curr = vec[sz(vec) - U - 1];
vec.pb(curr);
}
char GetLetter(int P)
{
int y = dep[curr] - P - 1;
int x = curr;
for(int i = 0;i <= 20;i++)
{
if(y & (1 << i))
{
x = p[x][i];
}
}
return val[x];
}
