#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
constexpr int N = 2e5 + 1;
constexpr int K = 101;
using bi = array<bitset<K>, 2>;
int n, k;
void f(vector<bi> &dp, string s, vector<int> a) {
vector<int> p(n + 2);
for (int i = 1; i <= n; i++) {
p[i] = p[i - 1] + (s[i] == '_');
}
auto good = [&](int l, int r) {
if (p[r] - p[l - 1] > 0) return false;
return (s[l - 1] != 'X' && s[r + 1] != 'X');
};
dp[0][0].set(0);
dp[0][1].set(0);
for (int i = 1; i <= n; i++) {
if (s[i] != 'X') {
dp[i][0] = dp[i - 1][0] | dp[i - 1][1];
}
for (int j = 1; j <= k; j++) {
if (s[i] != '_' && i >= a[j] && good(i - a[j] + 1, i)) {
if (dp[i - a[j]][0][j - 1]) {
dp[i][1].set(j);
}
}
}
}
}
string solve_puzzle(string s, vector<int> c) {
n = s.size();
k = c.size();
string t(n + 5, '!');
string s_rev(n + 5, '!');
for (int i = 1; i <= n; i++) {
t[i] = s[i - 1];
}
for (int i = n; i >= 1; i--) {
s_rev[n - i + 1] = s[i - 1];
}
vector<int> a = {0}, c_rev = {0};
for (int i = 1; i <= k; i++) {
a.push_back(c[i - 1]);
}
for (int i = k; i >= 1; i--) {
c_rev.push_back(c[i - 1]);
}
vector<bi> dp(n + 2), dp_rev(n + 2);
f(dp, t, a);
f(dp_rev, s_rev, c_rev);
string ans(n, '!');
vector<int> diff(n + 2);
for (int i = 1; i <= n; i++) {
for (int b = 1; b <= k; b++) {
if (dp[i][1][b] && dp_rev[n - i][0][k - b]) {
int L = i - a[b] + 1;
int R = i;
if (L < 1) continue;
diff[L]++;
diff[R + 1]--;
}
}
}
for (int i = 1; i <= n; i++) {
diff[i] += diff[i - 1];
}
for (int i = 1; i <= n; i++) {
bool w = false;
for (int x = 0; x <= k; x++) {
if (dp[i][0][x] && dp_rev[n - i + 1][0][k - x]) {
w = true;
}
}
if (w && !diff[i]) ans[i - 1] = '_';
else if (!w && diff[i]) ans[i - 1] = 'X';
else if (w && diff[i]) ans[i - 1] = '?';
else abort();
}
return ans;
}
