#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
string solve_puzzle(string s, vector<int> c) {
s = "_" + s;
int const N = s.size();
int const K = c.size();
vector<int> ps(N + 1, 0);
for (int i = 0; i < N; i++)
ps[i + 1] = s[i] == '_';
partial_sum(begin(ps), end(ps), begin(ps));
vector<vector<bool>> dp(N + 1, vector<bool>(K + 1, false));
dp[0][0] = true;
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= K; j++) {
dp[i][j] = dp[i][j] || (s[i - 1] != 'X' && dp[i - 1][j]);
if (j && i > c[j - 1] && s[i - c[j - 1] - 1] != 'X' && ps[i] - ps[i - c[j - 1]] == 0) {
dp[i][j] = dp[i][j] || dp[i - c[j - 1] - 1][j - 1];
}
}
}
vector<int> cX(N + 1, 0), c_(N, 0);
vector<vector<bool>> mark(N + 1, vector<bool>(K + 1, false));
mark[N][K] = true;
for (int i = N; i >= 1; i--) {
for (int j = K; j >= 0; j--) {
if (!mark[i][j])
continue;
if (s[i - 1] != 'X' && dp[i - 1][j]) {
mark[i - 1][j] = true;
c_[i - 1]++;
}
if (
j &&
i > c[j - 1] &&
s[i - c[j - 1] - 1] != 'X' &&
ps[i] - ps[i - c[j - 1]] == 0 &&
dp[i - c[j - 1] - 1][j - 1]
) {
mark[i - c[j - 1] - 1][j - 1] = true;
cX[i - c[j - 1]]++;
cX[i]--;
c_[i - c[j - 1] - 1]++;
}
}
}
partial_sum(begin(cX), end(cX), begin(cX));
string ans;
for (int i = 1; i < N; i++) {
if (s[i] != '.')
ans.push_back(s[i]);
else if (c_[i] && cX[i])
ans.push_back('?');
else if (c_[i])
ans.push_back('_');
else
ans.push_back('X');
}
return ans;
}
