#include<bits/stdc++.h>
#include "paint.h"
using namespace std;
string solve_puzzle(string s, vector<int> c) {
int n = s.size(), k = c.size();
auto check=[&]{
int pref1[n + 1], pref2[n + 1];
for(int i = 0; i < n; i++){
pref1[i + 1] = pref1[i] + (s[i] == '_');
pref2[i + 1] = pref2[i] + (s[i] == 'X');
}
int dp[k + 1][n + 1];
dp[0][0] = 1;
for(int i = 0; i < k; i++){
for(int j = 0; j < n; j++){
if(j + 1 < c[i]) continue;
for(int l = -1; l < j; l++){
if(l > j - c[i]) break;
if((l >= 0 && l == j - c[i]) || (pref1[j + 1] - pref1[j + 1 - c[i]] > 0 || pref2[j + 1 - c[i]] - pref2[l + 1] > 0)) continue;
dp[i + 1][j + 1] |= dp[i][l + 1];
}
if(i + 1 == k && dp[i + 1][j + 1]) if(pref2[n] - pref2[j + 1] == 0) return true;
}
}
return false;
};
string ans = s;
for(int i = 0;i < n; i++){
if(s[i] == '_' || s[i] == 'X') continue;
s[i] = '_';
int f1 = check();
s[i] = 'X';
int f2 = check();
s[i] = '.';
if(f1 && f2) ans[i]='?';
else if(f1) ans[i]='_';
else if(f2) ans[i]='X';
}
return ans;
}
