#include <bits/stdc++.h>
using namespace std;
struct node{
int l, r;
char val;
bool hasmin = 0;
int left, right;
};
const int dydis = 15000000;
node tree[dydis];
const int dd = 1e6 + 1;
int dbIndd = 0, dbInd ;
vector<int> roots;
int curPlace = 0;
void build(int v){
if(v >= dd){
tree[v].l = tree[v].r = dbIndd++;
tree[v].val = -1;
tree[v].hasmin = 1;
tree[v].left = tree[v].right = -1;
}else{
build(v*2); build(v*2+1);
tree[v].l = tree[v*2].l;
tree[v].r = tree[v*2+1].r;
tree[v].hasmin = 1;
tree[v].left = v*2;
tree[v].right = v*2+1;
}
}
void Init() {
build(1);
dbInd = dd*2 + 2;
roots.push_back(1);
}
int it = 0;
void addLast(int v, int ka){
//if(it++ > 20) exit(0);
//cout << "v = " << v << ", ka = " << ka << ", mano int: [" <<tree[v].l << "; " << tree[v].r << "]\n";
if(tree[v].l == tree[v].r){
tree[v].val = ka;
tree[v].hasmin = tree[v].val == -1;
//cout << "padarau " << tree[v].l << " i " << ka << endl;
//cout << "[" << tree[v].l << "; " << tree[v].r << "].hasmin = " << tree[v].hasmin << endl;
return;
}
if(tree[tree[v].left].hasmin){
// cout << "eisim i kaire!" << ", ten siaip yra " << tree[v].left << ", tai as ji nukopijuoju i " << dbInd << endl;
tree[dbInd] = tree[tree[v].left];
tree[v].left = dbInd;
addLast(dbInd++, ka);
}else{
tree[dbInd] = tree[tree[v].right];
tree[v].right = dbInd;
addLast(dbInd++, ka);
}
tree[v].hasmin = tree[tree[v].left].hasmin | tree[tree[v].right].hasmin;
//cout << "[" << tree[v].l << "; " << tree[v].r << "].hasmin = " << tree[v].hasmin << endl;
}
int getVal(int v, int x){
if(tree[v].r < x || x < tree[v].l) return 0;
if(tree[v].l == tree[v].r) return tree[v].val;
if(tree[v].l <= x && x <= tree[v].r){
return getVal(tree[v].left, x) + getVal(tree[v].right, x);
}else{
return 0;
}
}
void print(int v){
if(tree[v].l == tree[v].r){
if(tree[v].val == -1) return;
cout << ((char)('a' + tree[v].val));
return;
}
print(tree[v].left);
print(tree[v].right);
}
void TypeLetter(char L) {
//cout << "rasom " << L << " raide " << endl;
tree[dbInd] = tree[roots.back()];
//cout << "kol kas" << endl;
int bv = dbInd;
dbInd++;
addLast(dbInd-1, L-'a');
roots.push_back(bv);
//cout << "po typinant: "; print(roots.back());
//cout << endl;
}
void UndoCommands(int U) {
tree[dbInd] = tree[roots[roots.size()-1-U]];
roots.push_back(dbInd);
//cout << "po udno: "; print(roots.back());
//cout << endl;
dbInd++;
}
char GetLetter(int P) {
return ((char)('a' + getVal(roots.back(), P)));
}
