#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) { //[l, r)
assert(l < r);
return nxtBlack[l] >= r;
};
auto canBlack = [&](int l, int r) { //[l, r)
assert(l < r);
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);
}
}
vector last(k + 1, vector<int>(n + 1, -1)); //last good
iota(last[0].begin(), last[0].begin() + nxtBlack[0], 0);
fill(last[0].begin() + nxtBlack[0], last[0].end(), nxtBlack[0] - 1);
// cout << "pref:\n";
for (int i = 2; i < n - 2; ++i) {
for (int j = 1; j <= k; ++j) {
last[j][i] = last[j][i - 1];
int L = i - c[j - 1] + 1;
if (L >= 0 && canBlack(L, i + 1) && s[L - 1] != 'X') {
int p = last[j - 1][L - 2];
if (p != -1 && canWhite(p + 1, L)) {
pref[j][i] = true;
last[j][i] = i;
}
}
// cout << pref[j][i] << " ";
}
// cout << endl;
}
// cout << endl;
for (int i = 0; i <= k; ++i) {
fill(last[i].begin(), last[i].end(), -1);
}
iota(last[k].begin() + prvBlack[n - 1] + 1, last[k].end(), prvBlack[n - 1] + 1);
fill(last[k].begin(), last[k].begin() + prvBlack[n - 1] + 1, prvBlack[n - 1] + 1);
// cout << "suf\n";
for (int i = n - 3; i > 1; --i) {
for (int j = 0; j < k; ++j) {
last[j][i] = last[j][i + 1];
int R = i + c[j];
if (R <= n && canBlack(i, R) && s[R] != 'X') {
int p = last[j + 1][R + 1];
if (p != -1 && canWhite(R, p)) {
suf[j][i] = true;
last[j][i] = i;
}
}
// cout << suf[j][i] << " ";
}
// cout << endl;
}
for (int j = 0; j < k; ++j) {
vector<int> pntL(n);
for (int i = 1; i < n; ++i) {
auto goodL = [&]() {
return pref[j][pntL[i]] && canWhite(pntL[i] + 1, i);
};
if (i + c[j] - 1 < n && pref[j + 1][i + c[j] - 1]) {
pntL[i] = pntL[i - 1];
while (pntL[i] < i - 1 && !goodL()) {
++pntL[i];
}
}
}
vector<int> pntR(n, n - 1);
for (int i = n - 2; i > 0; --i) {
auto goodR = [&]() {
return suf[j + 1][pntR[i]] && canWhite(i + c[j], pntR[i]);
};
if (i + c[j] - 1 < n && pref[j + 1][i + c[j] - 1] && suf[j][i]) {
pntR[i] = pntR[i + 1];
while (pntR[i] > i + c[j] - 1 && !goodR()) {
--pntR[i];
}
if (pntL[i] < i - 1 && pntR[i] < n) {
setBlack(i, i + c[j]);
setWhite(pntL[i] + 1, i);
setWhite(i + c[j], pntR[i]);
}
}
}
}
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);
}
