#include <bits/stdc++.h>
/// 500 485 462 A4
using namespace std;
typedef int ll;
typedef complex<double> point;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
//#define endl '\n'
//#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
const int N=1e6+100,M=22;
ll par[N][M];
char c[N];
ll sz[N];
char last[N];
void mrg(ll u,ll v,bool b){
if (b==0){
sz[u]=sz[v];
last[u]=last[v];
for (int i=0;i<M;i++) par[u][i]=par[v][i];
}
else{
sz[u]=sz[v]+1;
last[u]=c[u];
par[u][0]=v;
// cout << v << " eorijto4rj " << endl;
for (int i=1;i<M;i++) par[u][i]=par[par[u][i-1]][i-1];
}
return ;
}
ll get(ll v,ll h){
for (int i=0;i<M;i++){
if (h & (1<<i)) v=par[v][i];
}
return v;
}
void Init(){
return ;
}
ll cnt=0;
vector <char> dd;
void TypeLetter(char L) {
dd.pb(L);
cnt++;
c[cnt]=L;
mrg(cnt,cnt-1,1);
// cout << last[cnt] << endl;
}
void UndoCommands(int U) {
for (int i=0;i<U;i++) dd.pop_back();
cnt++;
mrg(cnt,cnt-U-1,0);
}
char GetLetter(int P) {
return dd[P];
P=sz[cnt]-P;
P--;
// cout << P << endl;
if (P==0) return last[cnt];
ll z=get(cnt,P);
return c[z];
}
/*
int32_t main(){
Init();
int cmd_num;
int tmp = scanf("%d", &cmd_num);
assert(tmp == 1);
int i;
for (i = 0; i < cmd_num; i++) {
char cmd;
tmp = scanf(" %c", &cmd);
assert(tmp == 1);
if (cmd == 'T') {
char letter;
tmp = scanf(" %c", &letter);
assert(tmp == 1);
TypeLetter(letter);
}
else if (cmd == 'U') {
int number;
tmp = scanf("%d", &number);
assert(tmp == 1);
UndoCommands(number);
}
else if (cmd == 'P') {
int index;
char letter;
tmp = scanf("%d", &index);
assert(tmp == 1);
letter = GetLetter(index);
printf("%c\n", letter);
}
}
puts("Let's test for cheating!!");
return 0;
}
*/
