#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, k;
string s;
vector<int> c;
ll ans[100][100][100];
bool solve(ll i, ll j, ll x){
if(i==n && (j==k || (j==k-1 && x==c[j]))) return 1;
else if(i==n) return 0;
else if(ans[i][j][x]!=-1) return ans[i][j][x];
else if(j==k){ // Must be _
if(s[i]=='X') return ans[i][j][x]=0;
else return ans[i][j][x]=solve(i+1,j,x);
}
else if(x==c[j]){ // Must be _
if(s[i]=='X') return ans[i][j][x]=0;
else return ans[i][j][x]=solve(i+1,j+1,0);
}
else if(x>0){ // Must be X
if(s[i]=='_') return ans[i][j][x]=0;
else return ans[i][j][x]=solve(i+1,j,x+1);
}
else{ // Can be anything
if(s[i]=='_') return ans[i][j][x]=solve(i+1,j,x);
else if(s[i]=='X') return ans[i][j][x]=solve(i+1,j,x+1);
else return ans[i][j][x]=solve(i+1,j,x)||solve(i+1,j,x+1);
}
}
string solve_puzzle(string s1, vector<int> c1){
n=s1.size(); k=c1.size();
s=s1;
c=c1;
string t;
for(ll idx=0; idx<n; idx++){
// cout<<idx<<endl;
if(s[idx]!='.') t+=s[idx];
else{
for(ll i=0; i<n; i++){
for(ll j=0; j<k; j++){
for(ll x=0; x<=c[j]; x++){
ans[i][j][x]=-1;
}
}
ans[i][k][0]=-1;
}
s[idx]='_';
if(!solve(0,0,0)){
// cout<<idx<<": X"<<endl;
t+='X';
s[idx]='.';
continue;
}
for(ll i=0; i<n; i++){
for(ll j=0; j<k; j++){
for(ll x=0; x<=c[j]; x++){
ans[i][j][x]=-1;
}
}
ans[i][k][0]=-1;
}
s[idx]='X';
if(!solve(0,0,0)){
// cout<<idx<<": _"<<endl;
t+='_';
}
else{
// cout<<idx<<": ?"<<endl;
t+='?';
}
s[idx]='.';
// cout<<idx<<endl;
}
}
return t;
}
