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