#include <bits/stdc++.h>
using namespace std;
vector<int> b , w ;
vector<int> c;
string a ;
vector<int> p ;
int n , k ;
vector<vector<vector<int>>> mem(1e3,vector<vector<int>>(200,vector<int>(2,-1))) ;
bool theresno(int i , int j){
int minus = 0;
if(i) minus=p[i-1 ] ;
return p[j]==minus ;
}
bool dp(int i , int j , int color){
if(i==n&&j==k) return 1 ;
if(i>=n) return 0 ;
if(color&&a[i]=='X') return 0 ;
if(color==0&&a[i]=='_') return 0 ;
if(mem[i][j][(int)color]!=-1) return mem[i][j][color];
//if(i==3&&color) cout << 1 << " " ;
bool ok =1;//dp(i+1,j) ;
// if(i==2&&color==1) cout << i << " ";
if(j==k){
ok=dp(i+1,j,1) ;
if(ok)w[i] =1 ;
}
else{
if(color){
ok = dp(i+1,j,0)|dp(i+1,j,1) ;
if(ok) w[i]=1 ;
}
else{
ok = dp(i+c[j],j+1,1);
if(ok) ok&=theresno(i,i+c[j]-1) ;
if(ok) b[i]++;
if(ok&&i+c[j]<=n)b[i+c[j]]-- ;
}
}
mem[i][j][color]=ok ;
return ok ;
}
string solve_puzzle(string bb , vector<int> cc){
//int n , k ;
a = bb ;
c = cc ;
n = a.size() ;
k = c.size() ;
// cout << n <<" "<< k <<endl ;
b.resize(n+1);
w.resize(n+1) ;
p.resize(n+1) ;
for(int i=0;i<n;i++){
if(i) p[i]+=p[i-1] ;
p[i]+=(a[i]=='_');
}
dp(0,0,0) ;
dp(0,0,1) ;
vector<char> ans(n,'_') ;
for(int i=0;i<n;i++){
if(i) b[i]+=b[i-1] ;
// cout << b[i] << " " << w[i] << endl ;
if(b[i]&&w[i]) ans[i]='?' ;
else if(b[i]) ans[i]='X' ;
}
string rans ;
for(char x : ans)rans+=x ;
return rans ;
}
