#include <bits/stdc++.h>
#define N 1000005
#define ll long long int
#define MP make_pair
#define pb push_back
#define ppb pop_back
#define sp " "
#define endl "\n"
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll>
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define fast2 freopen ("badhair.gir","r",stdin);freopen ("badhair.cik","w",stdout);
#define mod 1000000007
#define fs(x,y) for(ll i=1;i<=y;i++) cin>>x[i]
#define fo(i,x,y) for(ll i=x;i<=y;i++)
#define INF 1000000000005
#define ull unsigned long long int
using namespace std;
char last,flag=1;
ll dad[N],cnt;
char s[N];
vector<char> v;
ll find(int x)
{
if(dad[x]==x)
return x;
return dad[x]=find(dad[x]);
}
void unite(int x,int y)
{
int dx=find(x);
int dy=find(y);
dad[dy]=dx;
}
void Init()
{
}
void TypeLetter(char L) {
flag=0;
s[++cnt]=L;
dad[cnt]=cnt;
last = L;
}
void UndoCommands(int U)
{
flag=0;
cnt++;
dad[cnt]=cnt;
unite(cnt-U-1,cnt);
}
char GetLetter(int P) {
ll x=cnt;
if(flag==1)
return v[P];
flag=1;
v.clear();
while(x>0)
{
x=find(x);
// cerr<<"[d]"<<sp<<x<<endl;
v.pb(s[x]);
x--;
}
reverse(v.begin(), v.end());
return v[P];
// return last;
}
