#include "paint.h"
#include <iostream>
#include <string>
#include <string.h>
#include <vector>
#include <cstdlib>
using namespace std;
long long mod=1e9+7;
long long dpst[200005][105][2];
long long dpdr[200005][105][2];
int v[200005];
int vec[1005];
int spar[200005][2];
string solve_puzzle(string s,vector<int> c) {
int n=s.size();
int k=c.size();
for(int i=1;i<=n;i++)
{
v[i]=s[i-1];
spar[i][0]=spar[i-1][0];
spar[i][1]=spar[i-1][1];
if(v[i]==88)
{
spar[i][1]++;
}
if(v[i]==95)
{
spar[i][0]++;
}
}
for(int i=1;i<=k;i++)
{
vec[i]=c[i-1];
}
dpst[0][0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=k;j++)
{
int dr=i+vec[j+1]-1;
if(v[i]!=95 && dr<=n && j<k)
{
if(spar[dr][0]-spar[i-1][0]==0)
{
dpst[dr][j+1][1]=(dpst[dr][j+1][1]+dpst[i-1][j][0])%mod;
}
}
if(v[i]!=88)
{
dpst[i][j][0]=(dpst[i][j][0]+dpst[i-1][j][0]+dpst[i-1][j][1])%mod;
}
}
}
dpdr[n+1][k][0]=1;
for(int i=n;i>=1;i--)
{
for(int j=k;j>=0;j--)
{
int st=i-vec[j]+1;
if(v[i]!=95 && st>=1 && j>=1)
{
if(spar[i][0]-spar[st-1][0]==0)
{
dpdr[st][j-1][1]=(dpdr[st][j-1][1]+dpdr[i+1][j][0])%mod;
}
}
if(v[i]!=88)
{
dpdr[i][j][0]=(dpdr[i][j][0]+dpdr[i+1][j][0]+dpdr[i+1][j][1])%mod;
}
}
}
long long fin=(dpst[n][k][0]+dpst[n][k][1])%mod;
string rez;
for(int i=1;i<=n;i++)
{
if(v[i]==88)
{
rez.push_back('X');
}
else if(v[i]==95)
{
rez.push_back('_');
}
else
{
long long tot=0;
for(int j=0;j<=k;j++)
{
tot=tot+(dpst[i-1][j][0]+dpst[i-1][j][1])*(dpdr[i+1][j][0]+dpdr[i+1][j][1])%mod;
}
if(tot==0)
{
rez.push_back('X');
}
else if(tot==fin)
{
rez.push_back('_');
}
else
{
rez.push_back('?');
}
}
}
return rez;
}
