#include"paint.h"
#include<cstdlib>
#include<iostream>
using namespace std;
string str;
vector<int>arr;
int n,m;
bool can_white[200000];
bool can_black[200000];
bool is_possible(int i,int j);
bool is_possible_directly(int i,int j){
if(j==m)
return false;
if(i+arr[j]>n)
return false;
for(int k=i;k<i+arr[j];k++)
if(str[k]=='_')
return false;
if(j!=m-1){
if(i+arr[j]>=n)
return false;
if(str[i+arr[j]]=='X')
return false;
return is_possible(i+arr[j]+1,j+1);
}
return is_possible(i+arr[j],j+1);
}
bool is_possible(int i,int j){
if(i==n)
return j==m;
if(str[i]=='_')
return is_possible(i+1,j);
bool nxt=is_possible_directly(i,j);
if(str[i]=='X')
return nxt;
return nxt||is_possible(i+1,j);
}
void recurse(int i,int j){
if(!is_possible(i,j))
return;
if(i==n)
return;
if(is_possible_directly(i,j)){
for(int k=i;k<i+arr[j];k++)
can_white[k]=true;
if(j==m-1){
can_black[i+arr[j]]=true;
recurse(i+arr[j],j+1);
}else
recurse(i+arr[j]+1,j+1);
}
if(is_possible(i+1,j)){
can_black[i]=true;
recurse(i+1,j);
}
}
string solve_puzzle(string s,vector<int>c){
str=s;
arr=c;
n=(int)s.size();
m=(int)c.size();
recurse(0,0);
string res;
res.resize(n);
for(int i=0;i<n;i++){
if(can_white[i]&&can_black[i])
res[i]='?';
else if(can_white[i])
res[i]='X';
else
res[i]='_';
}
return res;
}
