#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,sz[N],pw[N];
int jumpvertex[N][21];
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()
{
pw[0]=1;
fo(i,1,20)
pw[i]=pw[i-1]*2;
}
void TypeLetter(char L) {
flag=0;
s[++cnt]=L;
dad[cnt]=cnt;
last = L;
sz[cnt]=sz[find(cnt-1)]+1;
ll x=cnt;
ll y=find(x-1);
jumpvertex[x][0]=y;
fo(i,1,20)
jumpvertex[x][i]=jumpvertex[jumpvertex[x][i-1]][i-1];
}
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);
// v.pb(s[x]);
// x--;
// }
// reverse(v.begin(), v.end());
// return v[P];
// }
char GetLetter(int P)
{
P++;
ll x=find(cnt);
ll y=sz[x]-P;
// while(y)
// {
// cerr<<"[d2]"<<sp<<x<<sp<<y<<endl;
for(int i=20;i>=0;i--)
{
if(pw[i]<=y)
{
// cerr<<"[d3]"<<sp<<i<<endl;
y-=pw[i];
x=jumpvertex[x][i];
}
}
// cerr<<endl;
// fo(i,1,cnt)
// {
// cout<<"[d]"<<sp<<i<<endl;
// fo(j,0,3)
// {
// cout<<jumpvertex[i][j]<<sp;
// }
// cout<<endl;
// }
// cout<<endl;
// cerr<<x<<sp;
return s[x];
// }
}
