#include "paint.h"
#include <cstdlib>
#include<bits/stdc++.h>
using namespace std;
#define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
string res;
int N, K;
vector<int> C;
string S;
bool suf1[200010][101], pref1[200010][101];//negre (numai capete)
bool suf2[200010][101], pref2[200010][101];//albe
//sufix[i][j], indicele i, ultimele j
//prefix[i][j], indicele i, primele j
int sum[200010];
int sum2[200010][101], sum3[200010][101];
int get_sum(int l, int r){
return sum[r]-sum[l-1];
}
//numarul punctelor din dreapta, care sunt capete drepte ale portiunii j, si portiunea neagra a j-a contine punctul r
int get_sum2(int l, int j){
return sum2[min(l+C[j-1]-1, N) ][j]-sum2[l-1][j];
}
//numarul punctelor din stanga, care sunt capete stangi ale portiunii j, si portiunea neagra a j-a contine punctul r
int get_sum3(int r, int j){
return sum3[r][K-j+1]-sum3[max(r-C[j-1]+1-1, 1) ][K-j+1];
}
void build(){
for(int i=1; i<=N; i++){
sum[i]=sum[i-1];
if(S[i-1]=='_'){
sum[i]++;
}
}
pref2[0][0]=true;
for(int i=1; i<=N; i++){
for(int j=0; j<=K; j++){
if( (j>0) && (i>=(C[j-1])) && ( get_sum(i-C[j-1]+1, i)==0 ) && ( pref2[i-C[j-1] ][j-1] ) ){
pref1[i][j]=true;
}
if( (S[i-1]!='X') && ( (pref2[i-1][j]==true) || (pref1[i-1][j]==true) ) ){
pref2[i][j]=true;
}
}
}
suf2[N+1][0]=true;
for(int i=N; i>=1; i--){
for(int j=0; j<=K; j++){
if((j>0) && ( (i+C[K-j]-1)<=N ) && (get_sum(i, i+C[K-j]-1)==0 ) && (suf2[i+C[K-j] ][j-1]==true) ){
suf1[i][j]=true;
}
if( (S[i-1]!='X') && ( (suf1[i+1][j]==true) || (suf2[i+1][j]==true) ) ){
suf2[i][j]=true;
}
}
}
for(int i=1; i<=N; i++){
for(int j=0; j<=K;j++){
sum2[i][j]=sum2[i-1][j];
if( (pref1[i][j]==true) &&(suf2[i+1][K-j]==true) ){
sum2[i][j]++;
}
sum3[i][j]=sum3[i-1][j];
if( (suf1[i][j]==true) && (pref2[i-1][K-j]==true) ){
sum3[i][j]++;
}
}
}
}
void build_res(){
res.resize(N);
for(int i=0; i<N; i++){
res[i]='?';
}
for(int i=1; i<=N; i++){
bool black=false; bool white=false;
for(int j=0; j<=K; j++){
if( ( (j>0) && ( ( get_sum2(i, j)>0 ) ) ) || ( (j>0) && (get_sum3(i, j)) ) ){
black=true;
}
if( ( (pref2[i][j]==true) && ( (suf1[i+1][K-j]==true) || (suf2[i+1][K-j]==true) ) ) ){
white=true;
}
}
if( (white) && (black) ){
res[i-1]='?';
}
else{
if(white){
res[i-1]='_';
}
else{
res[i-1]='X';
}
}
}
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
N=s.length(); K=c.size();
C=c; S=s;
build();
build_res();
return res;
}
