#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) (int)(v).size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 1e7+7;
int up[N][20], loc[N], depth[N], timer, letnum, curloc;
char node[N];
void Init(){
}
void TypeLetter(char L) {
node[++letnum] = L;
up[letnum][0] = curloc;
loc[++timer] = letnum;
depth[letnum] = depth[curloc]+1;
for(int i = 1; i < 20; i++){
up[letnum][i] = up[up[letnum][i-1]][i-1];
}
curloc = letnum;
}
void UndoCommands(int U) {
curloc = loc[timer-U];
loc[++timer] = curloc;
}
char GetLetter(int P){
P++;
int to = curloc;
for(int i = 19; i >= 0; i--){
if(depth[up[to][i]] >= P){
to = up[to][i];
}
}
return node[to];
}
