#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pii pair<ll, pll>
#define pb push_back
#define fi first
#define se second
using namespace std;
const int N = 2e6 + 5;
const int M = 1300;
const ll mod = 1e9 + 7;
int n, m, t, cur, node, cnt, a[N], nchar, p[N][21], h[N];
char c[N];
void Init()
{
}
void TypeLetter(char L)
{
++nchar;
h[nchar] = h[cur] + 1;
p[nchar][0] = cur;
++cnt;
cur = nchar;
a[cnt] = nchar;
c[nchar] = L;
for(int i = 1; i <= 20; i ++)p[nchar][i] = p[p[nchar][i-1]][i-1];
}
void UndoCommands(int U)
{
cur = a[cnt - U];
++cnt;
a[cnt] = cur;
}
char GetLetter(int P)
{
int dis = h[cur] - P - 1;
int u = cur;
for(int i = 20; i >= 0; i --)
if((dis >> i) & 1)u = p[u][i];
return c[u];
}
