#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
std::string solve_puzzle(std::string s, std::vector<int> c) {
int n = (int)s.length();
int k = (int)c.size();
vector<int>pref(n + 1,0);
for (int i = 0;i<n;++i){
pref[i + 1] = pref[i] + (s[i] == '_');
}
vector<vector<vector<int>>>dp(n + 1,vector<vector<int>>(k + 1,vector<int>(2,-1)));
function<int(int,int,int)>solve = [&](int u,int v,bool ok){
if (u == n){
if (v != k)return dp[u][v][ok] = 0;
return dp[u][v][ok] = 1;
}
if (dp[u][v][ok]!=-1)return dp[u][v][ok];
if (v == k){
return dp[u][v][ok] = solve(u + 1,v,0);
}
int ans = 0 ;
if (u + c[v]<= n && !ok && !(pref[u + c[v]] - pref[u])){
ans += solve(u + c[v],v + 1,1);
}
if (s[v]!='X'){
ans +=solve(u + 1,v,0);
}
return dp[u][v][ok] = ans;
};
solve(0,0,0);
string answer(n,'?');
vector<int>all(n,0);
for (int i = 1;i<=k;++i){
vector<int>ans(n,0);
int total = 0;
for (int j = 0;j<=n;++j){
if (j - c[i - 1] >= 0){
for (int p = 1;p<=c[i - 1];++p){
if (dp[j][i][1]!= -1){
ans[j - p]+=dp[j][i][1];
all[j - p]+=dp[j][i][1];
}
}
}
if (dp[j][i][1]!=-1)
total+=dp[j][i][1];
}
for (int j = 0;j<n;++j){
if (ans[j] == total)answer[j] = 'X';
}
}
for (int i = 0;i<n;++i){
if (all[i] == 0){
answer[i] = '_';
}
}
return answer;
}
