#include "paint.h"
#include <bits/stdc++.h>
bool pd[200010][110][2];
int k,n,aib[200010],checkpoints[110][200010];
bool b[200010],w[200010],aint[200010];
void adauga(int poz,int val)
{
for(;poz<=n;poz+=(poz&(-poz)))
aib[poz]+=val;
}
int suma(int poz)
{
int ans=0;
for(;poz>0;poz-=(poz&(-poz)))
ans+=aib[poz];
return ans;
}
void adaugab(int poz,int b,int e,int bi,int ei)
{
if(aint[poz]==true||b>ei||e<bi)
return;
if(bi<=b&&e<=ei)
{
aint[poz]=true;
return;
}
adaugab(poz*2,b,(b+e)/2,bi,ei);
adaugab(poz*2+1,(b+e)/2+1,e,bi,ei);
}
bool black(int poz,int b,int e,int pozval)
{
if(b>pozval||e<pozval)
return 0;
if(aint[poz]==true||b==e)
{
return aint[poz];
}
return (black(poz*2,b,(b+e)/2,pozval)|black(poz*2+1,(b+e)/2+1,e,pozval));
}
std::string solve_puzzle(std::string s, std::vector<int> c)
{
std::string ans;
k=c.size();
n=s.size();
int nrb=0,nrw=0;
pd[0][0][0]=true;
for(int i=1;i<=n;++i)
{
if(s[i-1]=='X')
nrb++;
else if(s[i-1]=='_')
{
nrw++;
adauga(i,1);
}
if(nrb==0)
pd[i][0][0]=true;
for(int j=1;j<=k;++j)
{
if(i>=c[j-1]&&nrw-suma(i-c[j-1])==0)
pd[i][j][1]=pd[i-c[j-1]][j-1][0];
if(s[i-1]!='X')
pd[i][j][0]=(pd[i-1][j][0]|pd[i-1][j][1]);
}
}
checkpoints[k][0]=1;
checkpoints[k][1]=n;
for(int j=k;j>=1;--j)
{
int poza=1;
for(int i=checkpoints[j][1];i>=1;--i)
{
if(pd[i][j][0]==true)
w[i]=true;
if(pd[i][j][1]==true)
{
w[i-c[j-1]]=true;
adaugab(1,1,n,i-c[j-1]+1,i);
checkpoints[j-1][++checkpoints[j-1][0]]=i-c[j-1]-1;
if(pd[i][j][0]==false)
{
while(poza<=checkpoints[j][0]&&i<=checkpoints[j][poza])
++poza;
i=checkpoints[j][poza]+1;
}
}
}
}
for(int i=checkpoints[0][1];i>=1;--i)
w[i]=true;
for(int i=1;i<=n;++i)
b[i]=black(1,1,n,i);
for(int i=1;i<=n;++i)
if(w[i]&&b[i])
ans+='?';
else if(w[i])
ans+='_';
else if(b[i])
ans+='X';
return ans;
}
