#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5, M = 100;
int canb[3 * N], canw[3 * N], dp[N][M], n, m, cnt[N];
vector<int> c;
string s;
bool calc (int i = 0, int j = 0) {
if (i >= n) {
return j == m;
}
int &ret = dp[i][j];
if (~ret) {
return ret;
}
ret = 0;
if (s[i] != 'X' && calc(i + 1, j)) {
canw[i] = ret = 1;
}
if (j != m && cnt[i] >= c[j] && s[i] != '_' && (i + c[j] >= n || s[i + c[j]] != 'X') && calc(i + c[j] + 1, j + 1)) {
ret = 1;
++canb[i];
--canb[i + c[j]];
canw[i + c[j]] = 1;
}
return ret;
}
string solve_puzzle(string s, vector<int> c) {
::c = c;
::s = s;
n = s.size();
m = c.size();
int cn = 0;
for (int i = n - 1; ~i; --i) {
cn += s[i] != '_' ? 1 : -cn;
cnt[i] = cn;
}
memset(dp, -1, sizeof dp);
assert(calc());
for (int i = 0; i < n; ++i) {
if (i) {
canb[i] += canb[i - 1];
}
if (canb[i] && canw[i]) {
s[i] = '?';
}
else if (canb[i]) {
s[i] = 'X';
}
else {
s[i] = '_';
}
}
return s;
}
