int ops[1000005], prev[1000005][20], size[1000005], sz; void Init(){ } void TypeLetter(char L){ ops[sz] = L; if(sz) prev[sz][0] = sz-1; for (int i=1; i<20; i++) { prev[sz][i] = prev[prev[sz][i-1]][i-1]; } size[sz] = size[prev[sz][0]]+1; sz++; } void UndoCommands(int U){ prev[sz][0] = sz-U-1; for (int i=1; i<20; i++) { prev[sz][i] = prev[prev[sz][i-1]][i-1]; } size[sz] = size[prev[sz][0]]; sz++; } char GetLetter(int P){ int pos = sz-1; int obj = P+1; for (int i=19; i>=0; i--) { if(size[prev[pos][i]] >= obj){ pos = prev[pos][i]; } } return ops[pos]; }