#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
string solve_puzzle(string s, vector<int> c) {
int n = s.size(), m = c.size();
vector<int> sum(n + 1);
for (int i = 0; i < n; ++i) {
sum[i + 1] = sum[i] + (s[i] == '_');
}
vector<int> black(n + 1);
vector<vector<bool>> l(n + 1, vector<bool>(m + 1));
l[0][0] = true;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
if (s[i - 1] != 'X' && l[i - 1][j]) {
l[i][j] = true;
} else if (j && i >= c[j - 1] && sum[i] == sum[i - c[j - 1]]) {
if (j == 1) {
l[i][j] = l[i - c[j - 1]][j - 1];
} else if (i > c[j - 1]) {
l[i][j] = l[i - c[j - 1] - 1][j - 1] && s[i - c[j - 1] - 1] != 'X';
}
}
}
}
vector<vector<bool>> r(n + 1, vector<bool>(m + 1));
r[n][m] = true;
for (int i = n - 1; ~i; --i) {
for (int j = m; ~j; --j) {
if (j < m && i <= n - c[j] && sum[i] == sum[i + c[j]]) {
if (j == m - 1) {
r[i][j] = r[i + c[j]][j + 1];
} else if (i < n - c[j]) {
r[i][j] = r[i + c[j] + 1][j + 1] && s[i + c[j]] != 'X';
}
if (r[i][j]) {
bool ok = false;
if (!j) {
ok = l[i][j];
} else if (i) {
ok = l[i - 1][j] && s[i - 1] != 'X';
}
if (ok) {
++black[i];
--black[i + c[j]];
}
}
}
if (s[i] != 'X' && r[i + 1][j]) {
r[i][j] = true;
}
}
}
string ans = s;
for (int i = 0; i < n; ++i) {
black[i + 1] += black[i];
if (s[i] == '.') {
if (black[i]) {
bool white = false;
for (int j = 0; j <= m; ++j) {
if (l[i][j] && r[i + 1][j]) {
white = true;
break;
}
}
if (white) {
ans[i] = '?';
} else {
ans[i] = 'X';
}
} else {
ans[i] = '_';
}
}
}
return ans;
}
