#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
string solve_puzzle(string s, vector<int> c) {
s = "__" + s + "__";
int n = s.size(), k = c.size();
vector<int> nxtWhite(n + 1, n), nxtBlack(n + 1, n), prvBlack(n + 1, -1);
auto canWhite = [&](int l, int r, bool f = false) { //[l, r)
if (!f) assert(l < r && l >= 0 && r <= n);
return nxtBlack[l] >= r;
};
auto canBlack = [&](int l, int r, bool f = false) { //[l, r)
if (!f) assert(l < r && l >= 0 && r <= n);
return nxtWhite[l] >= r;
};
for (int i = n - 1; i > -1; --i) {
nxtBlack[i] = nxtBlack[i + 1];
nxtWhite[i] = nxtWhite[i + 1];
if (s[i] == '_') {
nxtWhite[i] = i;
} else if (s[i] == 'X') {
nxtBlack[i] = i;
}
}
for (int i = 0; i < n; ++i) {
if (i > 0) {
prvBlack[i] = prvBlack[i - 1];
}
if (s[i] == 'X') {
prvBlack[i] = i;
}
}
vector pref(k + 1, vector<bool>(n + 1)), suf(k + 1, vector<bool>(n + 1));
fill(pref[0].begin(), pref[0].begin() + nxtBlack[0], true), fill(suf[k].begin() + prvBlack[n - 1] + 1, suf[k].end(),
true);
vector<int> prefSum(k + 1), sufSum(k + 1);
for (int i = 0; i < k; ++i) {
prefSum[i + 1] = prefSum[i] + c[i];
}
for (int i = k - 1; i > -1; --i) {
sufSum[i] = sufSum[i + 1] + c[i];
}
vector<int> lazyWhite(n + 1), lazyBlack(n + 1);
auto setBlack = [&](int l, int r) { //[l, r)
lazyBlack[l] += 1;
lazyBlack[r] -= 1;
// cout << l << " " << r << endl;
if (l <= 3 && 3 < r) {
// cout << "hey :)" << endl;
}
};
auto setWhite = [&](int l, int r) { //[l, r)
lazyWhite[l] += 1;
lazyWhite[r] -= 1;
};
for (int i = 0; i < n; ++i) {
if (s[i] == 'X') {
setBlack(i, i + 1);
} else if (s[i] == '_') {
setWhite(i, i + 1);
}
}
// cout << "pref:\n";
for (int i = 2; i < n - 2; ++i) {
for (int j = 1; j <= k; ++j) {
int L = i - c[j - 1] + 1;
if (L >= 0 && canBlack(L, i + 1) && s[L - 1] != 'X') {
for (int p = L - 2; p > -1; --p) {
if (pref[j - 1][p] && canWhite(p + 1, L)) {
pref[j][i] = true;
break;
}
}
}
// cout << pref[j][i] << " ";
}
// cout << endl;
}
// cout << endl;
// cout << "suf\n";
for (int i = n - 3; i > 1; --i) {
for (int j = 0; j < k; ++j) {
int R = i + c[j];
if (R <= n && canBlack(i, R) && s[R] != 'X') {
for (int p = R + 1; p < n; ++p) {
if (suf[j + 1][p] && canWhite(R, p)) {
suf[j][i] = true;
break;
}
}
}
// cout << suf[j][i] << " ";
}
// cout << endl;
}
for (int j = 0; j < k; ++j) {
int pntL = 0, pntR = n - 1;
for (int i = 1; i < n; ++i) {
auto goodL = [&]() {
return pref[j][pntL] && canWhite(pntL + 1, i, 1);
};
auto goodR = [&]() {
return suf[j + 1][pntR] && canWhite(i + c[j], pntR, 1);
};
if (i + c[j] - 1 < n && pref[j + 1][i + c[j] - 1] && suf[j][i]) {
while (!goodL()) {
++pntL;
}
while (!goodR()) {
--pntR;
}
setBlack(i, i + c[j]);
setWhite(pntL + 1, i);
setWhite(i + c[j], pntR);
}
}
}
string ans(n, '?');
int sumWhite = 0, sumBlack = 0;
for (int i = 0; i < n; ++i) {
sumWhite += lazyWhite[i];
sumBlack += lazyBlack[i];
if (sumWhite && sumBlack) {
ans[i] = '?';
} else if (sumWhite) {
ans[i] = '_';
} else {
assert(sumBlack);
ans[i] = 'X';
}
}
return ans.substr(2, n - 4);
}
