#include"paint.h"
#include<cstdlib>
#include<iostream>
using namespace std;
string str;
vector<int>arr;
int n,m;
int can_white[200001];
bool can_black[200000];
int next_[200000];
bool is_possible(int i,int j);
bool dpt1[200001][101];
bool dp1[200001][101];
bool is_possible_directly(int i,int j){
if(dpt1[i][j])
return dp1[i][j];
dpt1[i][j]=true;
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(next_[i]<i+arr[j])
return false;
if(j==m-1){
dp1[i][j]=is_possible(i+arr[j],j+1);
return dp1[i][j];
}
if(i+arr[j]>=n)
return false;
if(str[i+arr[j]]=='X')
return false;
dp1[i][j]=is_possible(i+arr[j]+1,j+1);
return dp1[i][j];
}
bool dpt2[200001][101];
bool dp2[200001][101];
bool is_possible(int i,int j){
if(dpt2[i][j])
return dp2[i][j];
dpt2[i][j]=true;
if(i==n){
dp2[i][j]=j==m;
return dp2[i][j];
}
if(str[i]=='_'){
dp2[i][j]=is_possible(i+1,j);
return dp2[i][j];
}
bool nxt=is_possible_directly(i,j);
if(str[i]=='X'){
dp2[i][j]=nxt;
return dp2[i][j];
}
dp2[i][j]=nxt||is_possible(i+1,j);
return dp2[i][j];
}
bool vis[200001][201];
void recurse(int i,int j){
if(vis[i][j])
return;
vis[i][j]=true;
if(!is_possible(i,j))
return;
if(i==n)
return;
if(is_possible_directly(i,j)){
can_white[i]++;
can_white[i+arr[j]]--;
if(j==m-1)
recurse(i+arr[j],j+1);
else{
can_black[i+arr[j]]=true;
recurse(i+arr[j]+1,j+1);
}
}
if(is_possible(i+1,j)&&str[i]!='X'){
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();
int curr_=n;
for(int i=n-1;i>=0;i--){
if(str[i]=='_')
curr_=i;
next_[i]=curr_;
}
recurse(0,0);
string res;
res.resize(n);
int white=0;
for(int i=0;i<n;i++){
white+=can_white[i];
if(white&&can_black[i])
res[i]='?';
else if(white)
res[i]='X';
else
res[i]='_';
}
return res;
}
