#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5+10;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
int is_pos(string s, vector<int>& c){
int n=(int)s.size(), k=(int)c.size();
vector<vector<int>> dp(n+1, vector<int>(k+1, 0));
bool ok=0;
int lastW=-1;
for(int i=0;i<n;i++){
if(s[i]=='_') lastW=i;
if(i && s[i]!='X'){
for(int j=0;j<=k;j++)
dp[i][j]=dp[i-1][j];
}
else if(s[i]=='X') ok=1;
if(ok) dp[i][0]=0;
else dp[i][0]=1;
for(int j=1;j<=k;j++){
if(i+1<c[j-1] || i-lastW<c[j-1] || (i-c[j-1]>=0 && s[i-c[j-1]]=='X') || (i<n-1 && s[i+1]=='X')) continue;
if(i-c[j-1]-1<0){
if(j==1) dp[i][j]=1;
else dp[i][j]=0;
}
else dp[i][j]=(dp[i][j]|dp[i-c[j-1]-1][j-1]);
}
}
return dp[n-1][k];
}
string solve_puzzle(string s, vector<int> c) {
string ans="";
for(int i=0;i<(int)s.size();i++){
if(s[i]!='.') ans+=s[i];
else{
s[i]='X';
int bl=is_pos(s, c);
s[i]='_';
int wh=is_pos(s, c);
if(bl && wh) ans+='?';
else if(bl) ans+='X';
else ans+='_';
s[i]='.';
}
}
return ans;
}
