#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//#define int ll
using P = pair<int, int>;
#define all(x) x.begin(), x.end()
#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define sz(x) (int)x.size()
const char nl = '\n';
string solve_puzzle(string s, vector<int> c) {
int n = sz(s), k = sz(c);
bool dp1[n+1][k+1]; s = '&'+s;
memset(dp1, false, sizeof dp1);
vector<int> p(n+2);
rep(i, 1, n+1)
p[i] = (s[i] == '_')+p[i-1],
dp1[i][0] = 1;
vector<P> rng(k+1, {0, 101});
vector<int> cnt(k+1), z(n+3);
rep(j, 1, k+1) {
rep(i, 1, n+1) {
int len = c[j-1];
if (i < len)continue;
//if (j == 3 && i == 28)cout << p[i]-p[i-len] << nl;
if (p[i]-p[i-len] == 0 && (j==1|| (j>1 && i-len-1 >= 0 && dp1[i-len-1][j-1]))) {
dp1[i][j] = 1;
//cout << i-len+1 << " " << i << nl;
}
dp1[i][j] |= dp1[i-1][j];
}
}
//string ans;
//z[i] += 1, z[i+len] -= 1;
//cnt[j] += 1;
//rng[j] = {i, i+len-1};
bool dp2[n+4][k+2];
memset(dp2, false, sizeof dp2);
rep(i, n+1, 1)dp2[i][k+1] = true;
rep(j, k+1, 1) {
rep(i, n+1, 1) {
int len = c[j-1];
if (i+len-1 > n)continue;
if (p[i+len-1]-p[i-1] == 0 && (j==k||(j < k&&i+len+1 <= n && dp2[i+len+1][j+1]))) {
dp2[i][j] = 1;
//cout << i << " " << i+len-1 << nl;
}
dp2[i][j] |= dp2[i+1][j];
}
}
//rep(j, 1, k+1)
//rep(i, 1, n+1)dp1[i][j] |= dp1[i-1][j];
//cout << dp2[6][2] << nl;
rep(i, 1, k+1) {
rep(j, 1, n+1) {
int len = c[i-1];
bool ok = false;
if (i > 1 && j-2 >= 1)
ok = dp1[j-2][i-1];
else if (i == 1)ok = true;
if (i < k)
ok &= (j+len+1 <= n && dp2[j+len+1][i+1]);
if (j+len-1 > n)continue;
if (ok && p[j+len-1]-p[j-1] == 0) {
//cout << i << " " << j << nl;
z[j] += 1;
z[j+len] -= 1;
cnt[i] += 1;
rng[i] = {max(rng[i].first, j), min(rng[i].second,j+len-1)};
}
}
}
vector<int> b(n+1);
rep(i, 1, k+1)
if (rng[i].first <= rng[i].second) {
rep(j, rng[i].first, rng[i].second+1)b[j] = 1;
//cout << rng[i].first << " " << rng[i].second << nl;
}
string ans;
rep(i, 1, n+1) {
z[i] += z[i-1];
if (b[i])ans += 'X';
else if (z[i] == 0)ans += '_';
else ans += '?';
}
return ans;
}
