#include<bits/stdc++.h> using namespace std; #define maxn 1000005 struct node{ char val; node* l; node* r; }; int n,cur; int sz[maxn]; node* root[maxn]; void build(node* pos,int l,int r) { if(l==r) return ; int mid = (l+r)/2; pos->l = new node; pos->r = new node; build(pos->l,l,mid); build(pos->r,mid+1,r); } void upgrade(node* pos,node* last,int l,int r,int x,int val) { if(l==r) { pos->val = val; return ; } int mid = (l+r)/2; if(x<=mid) { pos->l = new node; pos->r = last->r; upgrade(pos->l,last->l,l,mid,x,val); } else { pos->l = last->l; pos->r = new node; upgrade(pos->r,last->r,mid+1,r,x,val); } } char query(node* pos,int l,int r,int x) { if(l==r) return pos->val; int mid = (l+r)/2; if(x<=mid) return query(pos->l,l,mid,x); return query(pos->r,mid+1,r,x); } void Init() { root[0] = new node; sz[0] = -1; build(root[0],0,1000000); } void TypeLetter(char L) { cur++; root[cur] = new node; sz[cur] = sz[cur-1] + 1; upgrade(root[cur],root[cur-1],0,1000000,sz[cur],L); } void UndoCommands(int U) { cur++; root[cur] = root[cur-U-1]; sz[cur] = sz[cur-U-1]; } char GetLetter(int P) { return query(root[cur],0,1000000,P); }