#include <bits/stdc++.h>
#include "paint.h"
#define sz(x) ((int)x.size())
using namespace std;
const int N = 200100;
const int K = 110;
string ans;
int n, k, res[N], ad[N], sf[N];
bool f[N][K][2], ff[N][K];
std::string solve_puzzle(std::string s, std::vector<int> c) {
s += "_";
n = sz(s);
k = sz(c);
sf[n] = 0;
for (int i = n - 1; i >= 0; i--)
sf[i] = sf[i + 1] + bool(s[i] == '_');
f[0][0][0] = 1;
for (int i = 0; i < n; i++)
for (int j = 0; j <= k; j++)
for (int tp = 0; tp < 2; tp++){
if (!f[i][j][tp]) continue;
if (s[i] == '_')
f[i + 1][j][0] = 1;
if (j < k) {
int len = c[j];
if (i + len + 1 <= n && sf[i] - sf[i + len] == 0 && s[i + len] != 'X')
f[i + len + 1][j + 1][1] = 1;
}
}
ff[n + 1][0] = 1;
for (int i = n + 1; i > 1; i--)
for (int j = 0; j <= k; j++){
if (!ff[i][j]) continue;
if (s[i - 2] == '_')
ff[i - 1][j] = 1;
if (j < k){
int len = c[k - 1 - j];
if (i - len - 1 >= 0 && sf[i - len - 1] - sf[i - 1] == 0){
int pos = i - len - 2;
if (pos < 0 || s[pos] != 'X')
ff[i - len - 1][j + 1] = 1;
}
}
}
for (int i = 1; i <= n; i++)
for (int kl = 0; kl <= k; kl++) {
if ((f[i][kl][0] || f[i][kl][1]) && ff[i][k - kl])
res[i] = 2;
if (f[i][kl][1] && ff[i][k - kl]){
int len = c[kl - 1];
ad[i - len]++;
ad[i]--;
}
}
int sm = 0;
for (int i = 1; i <= n; i++){
sm += ad[i];
res[i] |= bool(sm > 0);
}
for (int i = 1; i < n; i++){
if (res[i] == 1)
ans += "X";
else if (res[i] == 2)
ans += "_";
else ans += "?";
}
return ans;
}
