/*input
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;
#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"
const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;
template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }
template<typename T>
void print(vector<T> vec, string name = "") {
cout << name;
for (auto u : vec)
cout << u << ' ';
cout << '\n';
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct node {
char val;
int prior;
int cnt;
node *left = NULL, *right = NULL;
node(char a) : val(a), prior(rng()), cnt(1) { }
node(node *kit) {
val = kit->val;
prior = kit->prior;
cnt = kit->cnt;
left = kit->left;
right = kit->right;
}
};
inline int cnt(node *t) { return (t ? t->cnt : 0); }
inline void upd_cnt(node *t) { if (t) t->cnt = cnt(t->left) + cnt(t->right) + 1; }
void merge(node *&t, node *l, node *r) {
if (!l or !r)
t = (l ? l : r);
else if (l->prior < r->prior)
merge(r->left, l, r->left), t = r;
else
merge(l->right, l->right, r), t = l;
upd_cnt(t);
}
void split(node *t, int key, node *&l, node *&r, int add = 0) {
if (!t)
return void(l = r = NULL);
int imp_key = add + cnt(t->left);
if (key <= imp_key)
split(t->left, key, l, t->left, add), r = t;
else
split(t->right, key, t->right, r, imp_key + 1), l = t;
upd_cnt(t);
}
void insert(node *&curr, node *ka) {
if (!curr) curr = ka;
else if (ka->prior > curr->prior) {
ka->left = curr;
curr = ka;
// split(curr, ka->key, ka->left, ka->right), curr = ka;
} else {
if (!curr->right) {
insert(curr->right, ka);
} else {
node *naujas = new node(curr->right);
insert(naujas, ka);
curr->right = naujas;
}
}
upd_cnt(curr);
}
// void insert(node *&curr, node *ka) {
// if (!curr)
// curr = ka;
// else if (ka->prior > curr->prior)
// split(curr, ka->key, ka->left, ka->right), curr = ka;
// else
// insert(ka->key < curr->key ? curr->left : curr->right, ka);
// }
char gauk(node *curr, int k) {
int imp_key = cnt(curr->left);
// printf("k = %d, imp_key = %d, currval = %c\n", k, imp_key, curr->val);
if (imp_key == k) return curr->val;
else if (imp_key < k)
return gauk(curr->right, k - imp_key - 1);
else
return gauk(curr->left, k);
}
vector<node*> buvo;
char last;
void Init() {
// buvo.push_back(new node(' '));
}
void TypeLetter(char L) {
// printf("type L = %c\n", L);
if (buvo.empty()) {
buvo.push_back(new node(L));
} else {
buvo.push_back(new node(buvo.back()));
insert(buvo.back(), new node(L));
}
last = L;
}
void UndoCommands(int U) {
// printf("Undo U = %d\n", U);
// printf("kit = %d\n", (int)buvo.size() - 1 - U);
node *naujas = new node(buvo[buvo.size() - 1 - U]);
buvo.push_back(naujas);
}
char GetLetter(int P) {
// printf("gaunu P = %d\n", P);
assert(buvo.size());
return gauk(buvo.back(), P);
}
