#include <bits/stdc++.h>
using namespace std;
struct node{
char val;
bool hasmin = 0;
int left, right;
};
const int dydis = 20000000 + 1;
node tree[dydis];
const int dd = 1e5 + 1;
int dbIndd = 0, dbInd ;
vector<int> roots;
int curPlace = 0;
void build(int v){
if(v >= dd){
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].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;
int mid;
void addLast(int v, int ka, int tl = 0, int tr = -2){
if(tr == -2) tr = dd-1;
mid = (tl + tr) / 2;
//if(it++ > 20) exit(0);
//cout << "v = " << v << ", ka = " << ka << ", mano int: [" <<tree[v].l << "; " << tree[v].r << "]\n";
if(tl == tr){
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, tl, mid);
}else{
tree[dbInd] = tree[tree[v].right];
tree[v].right = dbInd;
addLast(dbInd++, ka, mid+1, tr);
}
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, int tl = 0, int tr = -2){
if(tr == -2) tr = dd-1;
if(tr < x || x < tl) return 0;
mid = (tl + tr) / 2;
// cout << "esu " << tl << "; " << tr << ", mid = " << mid << ", kaimynai [" << tl << "; " << mid << "], [" << mid+1 << "; " << tr << "]\n";
if(tl == tr){
// cout << "ret " << tl << endl << endl;
return tree[v].val;
}
if(tl <= x && x <= tr){
return getVal(tree[v].left, x, tl, mid) + getVal(tree[v].right, x, mid+1, tr);
}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)));
}
