#include "paint.h"
#include <bits/stdc++.h>
#define MAXN 400007
#define MAXK 107
using namespace std;
bool dpl[MAXK][MAXN],dpr[MAXK][MAXN],mb[MAXN],mc[MAXN];
int nz[MAXN],lw[MAXN],nw[MAXN];
std::string solve_puzzle(std::string s, std::vector<int> c)
{
int n=s.size()+2,k=c.size();
for(int i=2;i<n;i++)
{
if(s[i-2]=='X') nz[i]=0;
if(s[i-2]=='_') nz[i]=1;
if(s[i-2]=='.') nz[i]=2;
}
nz[1]=nz[n]=1;
dpl[0][0]=true;
for(int i=1;i<=n;i++) for(int j=0;j<=k;j++)
{
if(nz[i]) dpl[j][i]=dpl[j][i-1];
if(nz[i]==1) lw[i]=i;
else lw[i]=lw[i-1];
if(j>0 && i>=lw[i]+c[j-1] && dpl[j-1][i-c[j-1]-1] && nz[i-c[j-1]]) dpl[j][i]=true;
}
dpr[k+1][n+1]=true;
for(int i=n;i>0;i--) for(int j=k+1;j>0;j--)
{
if(nz[i]) dpr[j][i]=dpr[j][i+1];
if(nz[i]==1) nw[i]=i;
else nw[i]=nw[i+1];
if(j<=k && i+c[j-1]<=nw[i] && dpr[j+1][i+c[j-1]+1] && nz[i+c[j-1]]) dpr[j][i]=true;
}
for(int i=2;i<n;i++) for(int j=0;j<=k;j++) if(dpl[j][i-1] && dpr[j+1][i+1]) mb[i-2]=true;
for(int j=1;j<=k;j++)
{
int nd=1;
for(int i=2;i<n;i++)
{
if(dpl[j-1][i-2] && dpr[j+1][i+c[j-1]+1] && nz[i-1] && nz[i+c[j-1]] && nw[i]>=i+c[j-1]) nd=i+c[j-1]-1;
if(i<=nd) mc[i-2]=true;
}
}
string res="";
for(int i=0;i<n;i++)
{
if(s[i]!='.') res+=s[i];
else
{
if(mb[i] && mc[i]) res+='?';
if(mb[i] && !mc[i]) res+='_';
if(!mb[i] && mc[i]) res+='X';
}
}
return res;
}
