#include<bits/stdc++.h>
#include "paint.h"
//#pragma GCC optimize("trapv")
#define I inline void
using namespace std ;
using ll = long long ;
using ld = long double ;
const int N = 1e6 + 7 , mod = 1e9 + 7 ;
// How interesting!
int n , k ;
string S ;
std::vector<int> gc;
int mask[N] ;
bool viz[200005][103] ;
bool dp[200005][103] ;
int pre[N] ;
bool solve(int i , int j){
if(viz[i][j])
return dp[i][j] ;
viz[i][j] = 1;
if(i >= n)
return dp[i][j] = (j == k) ;
bool ret = 0 ;
if(j < k){
if( i + gc[j] <= n && S[i+gc[j]] != 'X'){
bool bad = !!(pre[i+gc[j]-1] - (i?pre[i-1]:0));
if(!bad && solve(i+gc[j] + 1 , j+1)){
ret = 1;
for(int r = i ;r < i + gc[j] ;r++){
mask[r]|=1 ;
}
mask[i+gc[j]]|=2 ;
}
}
}
if(S[i] != 'X' && solve(i+1 , j)){
ret = 1;
mask[i] |= 2 ;
}
return dp[i][j] = ret ;
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
gc = c ;
S = s + '.' ;
n = (int) s.size() ;
k = (int) c.size() ;
for(int i = 0 ;i < n;i++){
pre[i] = (S[i] == '_') ;
if(i)pre[i] += pre[i-1] ;
}
solve(0 , 0) ;
for(int i = 0 ;i < n;i++){
if(s[i] == '.'){
if(mask[i] == 3)
s[i] = '?' ;
else if(mask[i] == 1)
s[i] = 'X' ;
else if(mask[i] == 2)
s[i] = '_' ;
}
}
return s;
}
