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