//
// Created by adavy on 2/11/2023.
//
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using ll = long long;
using ld = long double;
using db = double;
using str = string; // yay python!
using ii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vii = vector<ii>;
using vpl = vector<pl>;
using vpd = vector<pd>;
#define tcT template<class T
#define tcTU tcT, class U
tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
tcT> using PR = pair<T,T>;
// pairs
#define mp make_pair
#define f first
#define s second
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
#define len(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!!
const int lg = 24;
struct Node{
char c;
int dp;
vector<Node*> par;
Node(char c) {
dp = 0;
par.rsz(lg);
this->c = c;
par[0] = this;
for(int j=1;j<lg;++j){
par[j] = par[j-1]->par[j-1];
}
}
Node(char c, Node* parent){
par.rsz(lg);
this-> dp = parent->dp+1;
this->c = c;
par[0] = parent;
for(int j=1;j<lg;++j){
par[j] = par[j-1]->par[j-1];
}
}
char lift(int n){
Node* cur = this;
F0R(j,lg) if (n&(1<<j)) cur = cur->par[j];
return cur->c;
}
};
vector<Node*> ops;
int cur;
void Init() {
Node* nd = new Node('$');
cur = 0;
ops.pb(nd);
}
void TypeLetter(char L) {
Node* nd = new Node(L, ops[cur]);
cur++;
ops.pb(nd);
}
void UndoCommands(int U) {
Node* nd = ops[cur-U];
ops.pb(nd);
cur++;
}
char GetLetter(int P) {
//cout << "cur" << ops[cur]->dp-1-P << endl;
return ops[cur]->lift( ops[cur]->dp-1-P);
}
/*
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
int tmp;
int main() {
Init();
int cmd_num;
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;
}
*/
