#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
using vb = vector<bool>;
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
using bs = bitset<101>;
vector<bs> calcDP(string s, const vi &c) {
const int n = sz(s), k = sz(c);
vi pref(n + 1);
pref[0] = 0;
forn(i, n) pref[i + 1] = pref[i] + (s[i] == '_');
vector<vector<bs>> dp(n + 1, vector<bs>(2));
dp[0][0][0] = true;
vector<bs> ret(n + 1);
forn(i, n) {
forn(j, k + 1) forn(last, 2) if (dp[i][last][j]) {
if (s[i] != 'X') dp[i + 1][0][j] = true;
if (last == 0 && j < k && i + c[j] <= n && pref[i + c[j]] - pref[i] == 0) {
dp[i + c[j]][1][j + 1] = true;
}
}
ret[i] = dp[i][0];
dp[i].clear();
}
ret[n] = dp[n][0];
dp[n].clear();
return ret;
}
string solve_puzzle(string s, vi c) {
const int n = sz(s), k = sz(c);
vi pref(n + 1);
pref[0] = 0;
forn(i, n) pref[i + 1] = pref[i] + (s[i] == '_');
vector<bs> dpPref = calcDP(s, c);
reverse(all(s)), reverse(all(c));
vector<bs> dpSuff = calcDP(s, c);
reverse(all(s)), reverse(all(c));
vi checkBlack(n + 1, 0);
forn(i, n) forn(j, k) if (dpPref[i][j] && i + c[j] <= n && pref[i + c[j]] - pref[i] == 0 && dpSuff[n - i - c[j]][k - j - 1]) {
checkBlack[i]++;
checkBlack[i + c[j]]--;
}
forn(i, n) checkBlack[i + 1] += checkBlack[i];
string ret = "";
forn(i, n) {
bool checkWhite = false;
forn(j, k + 1) {
checkWhite |= dpPref[i + 1][j] && dpSuff[n - i][k - j];
}
if (checkBlack[i] && checkWhite) {
ret += '?';
} else if (checkBlack[i]) {
ret += 'X';
} else if (checkWhite) {
ret += '_';
} else {
assert(false);
}
}
return ret;
}
