#include "paint.h"
#include <bits/stdc++.h>
bool pd[200010][110][2];
int k,n,aibb[200010],aibw[200010];
bool b[200010],w[200010];
void adaugab(int poz,int val)
{
for(;poz<=n;poz+=(poz&(-poz)))
aibb[poz]+=val;
}
int sumab(int poz)
{
int ans=0;
for(;poz>0;poz-=(poz&(-poz)))
ans+=aibb[poz];
return ans;
}
void adaugaw(int poz,int val)
{
for(;poz<=n;poz+=(poz&(-poz)))
aibw[poz]+=val;
}
int sumaw(int poz)
{
int ans=0;
for(;poz>0;poz-=(poz&(-poz)))
ans+=aibw[poz];
return ans;
}
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,pozmax=n,pozac;
pd[0][0][0]=true;
for(int i=1;i<=n;++i)
{
if(s[i-1]=='X')
{
nrb++;
adaugab(i,1);
}
else if(s[i-1]=='_')
{
nrw++;
adaugaw(i,1);
}
if(nrb==0)
pd[i][0][0]=true;
for(int j=1;j<=k;++j)
{
if(i>=c[j-1]&&nrw-sumaw(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]);
}
}
for(int j=k;j>=1;--j)
{
pozac=pozmax;
for(int i=pozac;i>=1;--i)
{
if(pd[i][j][0]==true)
w[i]=true;
if(pd[i][j][1]==true)
{
w[i-c[j-1]]=true;
for(int q=0;q<c[j-1];++q)
b[i-q]=true;
if(pozac==pozmax)
pozmax=i-c[j-1]-1;
if(pd[i][j][0]==false)
break;
}
}
}
for(int i=pozmax;i>=1;--i)
w[i]=true;
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;
}
