#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 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; L[root[0]] = R[root[0]] = root[0]; } 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); }