#include "paint.h"
#include <cassert>
#include <cstdlib>
#include <iostream>
using namespace std;
const int MAXN = 2e5 + 5;
const int MAXK = 105;
int n, k;
int pb[MAXN], pw[MAXN];
bool dp_pref[MAXN][MAXK][2], dp_suff[MAXN][MAXK][2];
int bcnt[MAXN];
int sum(int *pref, int lo, int hi) { return pref[hi] - pref[lo - 1]; }
string solve_puzzle(string s, vector<int> c) {
n = (int)s.size();
k = (int)c.size();
for (int i = 0; i < (int)s.size(); ++i) {
pb[i + 1] = pb[i] + (s[i] == 'X');
pw[i + 1] = pw[i] + (s[i] == '_');
}
dp_pref[0][0][0] = dp_pref[0][0][1] = true;
for (int i = 1; i <= n && s[i - 1] != 'X'; ++i)
dp_pref[i][0][0] = dp_pref[i][0][1] = true;
dp_suff[n + 1][k + 1][0] = dp_suff[n + 1][k + 1][1] = true;
for (int i = n; i >= 1 && s[i - 1] != 'X'; --i)
dp_suff[i][k + 1][0] = dp_suff[i][k + 1][1] = true;
for (int j = 1; j <= k; ++j) {
for (int i = 1; i <= n; ++i) {
if (s[i - 1] != 'X')
dp_pref[i][j][0] |= dp_pref[i - 1][j][0] | dp_pref[i - 1][j][1];
dp_pref[i][j][1] |= i >= c[j - 1] && sum(pw, i - c[j - 1] + 1, i) == 0 &&
dp_pref[i - c[j - 1]][j - 1][0];
}
}
for (int j = k; j >= 1; --j) {
for (int i = n; i >= 1; --i) {
if (s[i - 1] != 'X')
dp_suff[i][j][0] |= dp_suff[i + 1][j][0] | dp_suff[i + 1][j][1];
dp_suff[i][j][1] |= i + c[j - 1] - 1 <= n &&
sum(pw, i, i + c[j - 1] - 1) == 0 &&
dp_suff[i + c[j - 1]][j + 1][0];
}
}
assert(dp_pref[n][k][0] || dp_pref[n][k][1]);
assert(dp_suff[1][1][0] || dp_suff[1][1][1]);
for (int i = 0; i < n; ++i) {
for (int j = 1; j <= k; ++j) {
if (dp_pref[i + 1][j][1] && dp_suff[i + 2][j + 1][0]) {
bcnt[i - c[j - 1] + 1]++;
bcnt[i + 1]--;
}
}
}
string ret = "";
int bsum = 0;
for (int i = 0; i < n; ++i) {
bsum += bcnt[i];
if (s[i] != '.') {
ret.push_back(s[i]);
continue;
}
bool black = bsum > 0, white = false;
for (int j = 0; j <= k; ++j) {
white |=
(dp_pref[i + 1][j][0] &&
(dp_suff[i + 2][j + 1][0] || dp_suff[i + 2][j + 1][1])) ||
((dp_pref[i][j][0] || dp_pref[i][j][1]) && dp_suff[i + 1][j + 1][0]);
}
assert(black || white);
if (black && !white) {
ret.push_back('X');
continue;
}
if (!black && white) {
ret.push_back('_');
continue;
}
ret.push_back('?');
}
return ret;
}
