#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 69;
const int MAXK = 107;
bitset<MAXN> vst[MAXK];
bitset<MAXN> dp[MAXK][2];
int X[MAXN], _[MAXN];
int pfx[2][MAXN];
string solve_puzzle(string s, vector<int> c)
{
int N = (int)s.size(), K = (int)c.size();
for (int i = 0; i < N; ++i)
X[i+1] = X[i] + (s[i] == 'X');
for (int i = 0; i < N; ++i)
_[i+1] = _[i] + (s[i] == '_');
const auto solve = [&](const auto &self, int i, int j) -> bool
{
if (j == K)
return i <= N+1 && (i == N+1 || X[N] - X[i] == 0);
if (i >= N)
return false;
if (vst[j][i])
return dp[j][0][i] || dp[j][1][i];
vst[j][i] = true;
if (s[i] != 'X')
dp[j][0][i] = dp[j][0][i] | self(self, i+1, j);
if (i + c[j] <= N && _[i + c[j]] - _[i] == 0 && (i + c[j] == N || s[i + c[j]] != 'X'))
dp[j][1][i] = dp[j][1][i] | self(self, i+c[j]+1, j+1);
return dp[j][0][i] || dp[j][1][i];
};
solve(solve, 0, 0);
for (int j = 0; j < K; ++j)
{
for (int i = 0; i < N; ++i)
{
if (dp[j][0][i])
pfx[0][i]++, pfx[0][i+1]--;
if (dp[j][1][i])
{
pfx[1][i]++;
pfx[1][i + c[j]]--;
pfx[0][i + c[j]]++;
if (j+1 < K) pfx[0][i + c[j] + 1]--;
}
}
}
for (int j = 0; j < 2; ++j)
for (int i = 1; i < N; ++i)
pfx[j][i] += pfx[j][i-1];
for (int i = 0; i < N; ++i)
{
if (pfx[0][i] && pfx[1][i])
s[i] = '?';
else if (pfx[0][i])
s[i] = '_';
else s[i] = 'X';
}
return s;
}
