#include <bits/stdc++.h>
using namespace std;
const long long INFll = 1e18+10;
const int INFii = 1e9+10;
typedef long long ll;
typedef int ii;
typedef double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define maxn 1000100
#define log 22
//LEMBRAR DE MUDAR
ii n, tmp, p[maxn][log+2], t[maxn], h[maxn];
char c[maxn];
void TypeLetter(char L) {
n++;
tmp++;
t[tmp] = n;
c[n] = L;
p[n][0] = t[tmp-1];
h[n] = h[t[tmp-1]] + 1;
for(ii i = 1; i <= log; i++) {
p[n][i] = p[p[n][i-1]][i-1];
}
//cout << L << " " << n << " " << tmp << " -> " << h[n] << endl;
}
void UndoCommands(int U) {
tmp++;
t[tmp] = t[tmp-U-1];
}
char GetLetter(int P) {
ii u = t[tmp];
P = h[t[tmp]]-P-1;
for(ii i = log; i >= 0; i--) {
if(P-(1<<i) >= 0) {
P-= (1<<i);
u = p[u][i];
}
}
return c[u];
}
void Init() {
}
