#include<bits/stdc++.h>
#include "paint.h"
#define fi first
#define se second
using namespace std;
bool ok[200010][110][2];
bool okk[200010][110][2];
int ch[200010];
string solve_puzzle(string s,vector<int> c)
{
int n=s.size(),k=c.size(),a,b,i,j;
a=-1;b=-n-10;
for(i=0;i<n;i++)
{
if(s[i]=='_')
a=i;
if(s[i]=='X')
b=i;
if(b<0)
ok[i][0][0]=true;
for(j=1;j<=k;j++)
{
if(i>0 && s[i]!='X' && ok[i-1][j][0])
ok[i][j][0]=true;
if(a+c[j-1]<=i && b!=i-c[j-1]
&& ((i-c[j-1]-1<0 && j==1) || (i-c[j-1]-1>=0 && ok[i-c[j-1]-1][j-1][0])))
okk[i][j][0]=ok[i][j][0]=true;
}
}
a=n;b=2*n+10;
for(i=n-1;i>=0;i--)
{
if(s[i]=='_')
a=i;
if(s[i]=='X')
b=i;
if(b>n)
ok[i][k+1][1]=true;
for(j=1;j<=k;j++)
{
if(i<n-1 && s[i]!='X' && ok[i+1][j][1])
ok[i][j][1]=true;
if(a-c[j-1]>=i && b!=i+c[j-1]
&& ((i+c[j-1]+1>=n && j==k) || (i+c[j-1]+1<n && ok[i+c[j-1]+1][j+1][1])))
okk[i][j][1]=ok[i][j][1]=true;
}
}
for(i=0;i<n;i++)
{
for(j=1;j<=k;j++)
{
if(okk[i][j][1] && okk[i+c[j-1]-1][j][0])
{
//cerr<<j<<" ["<<i<<","<<i+c[j-1]-1<<"]\n";
ch[i]++;
ch[i+c[j-1]]--;
}
}
}
for(i=0;i<n;i++)
{
if(i>0)
ch[i]+=ch[i-1];
bool wh=false,bl=(ch[i]>0);
for(j=0;j<=k;j++)
{
if(s[i]!='X' && ((i==0 && j==0) || (i>0 && ok[i-1][j][0]))
&& ((i==n-1 && j==k) || (i<n-1 && ok[i+1][j+1][1])))
{
wh=true;
break;
}
}
if(!wh)
s[i]='X';
else if(!bl)
s[i]='_';
else
s[i]='?';
}
return s;
}
