#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
long long n,m,ps[200069];
bitset<269> dp[2][200069];
long long qr(long long lh,long long rh)
{
if(lh>rh)
{
swap(lh,rh);
}
return ps[rh]-ps[lh-1];
}
string solve_puzzle(string s,vector<int> a)
{
long long i,j,ii,u,tg;
n=s.length();
m=a.size();
for(i=1;i<=n;i++)
{
ps[i]=ps[i-1]+(s[i-1]=='_');
}
for(ii=0;ii<2;ii++)
{
u=!ii*2-1;
dp[ii][(n+1)*ii][m*2*ii]=1;
for(i=1+(n-1)*ii;i&&i<=n;i+=u)
{
for(j=0;j<=m*2;j++)
{
if(j%2==0)
{
if(s[i-1]!='X')
{
dp[ii][i][j]=dp[ii][i-u][j];
if(j-u>=0&&j-u<=m*2)
{
dp[ii][i][j]=dp[ii][i][j]|dp[ii][i-u][j-u];
}
}
}
else
{
tg=i-a[j/2]*u;
if(tg>=0&&tg<=n+1&&!qr(i,tg+u))
{
dp[ii][i][j]=dp[ii][tg][j-u];
}
}
}
}
}
for(i=1;i<=n;i++)
{
ps[i]=0;
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m*2;j+=2)
{
if(dp[0][i][j]&&dp[1][i+1][j+1])
{
ps[i-a[j/2]+1]++;
ps[i+1]--;
}
}
}
s="";
for(i=1;i<=n;i++)
{
ps[i]+=ps[i-1];
if(!ps[i])
{
s+='_';
}
else
{
for(j=0;j<=m*2;j+=2)
{
if(dp[0][i][j]&&dp[1][i][j])
{
j=-1;
break;
}
}
if(j!=-1)
{
s+='X';
}
else
{
s+='?';
}
}
}
return s;
}
