#include <bits/stdc++.h>
using namespace std;
string solve_puzzle(string s, vector<int> c) {
int n = s.length() + 1, k = c.size();
s = " " + s;
int pw[n] = {}, pb[n] = {}, black[n] = {};
for (int i = 1; i < n; i++)
pw[i] = pw[i - 1] + (s[i] == '_'), pb[i] = pb[i - 1] + (s[i] == 'X');
bool dp1[n][k] = {}, check1[n][k] = {};
for (int i = c[0]; i < n; i++) {
dp1[i][0] = pw[i] - pw[i - c[0]] == 0 && pb[i - c[0]] - pb[0] == 0;
check1[i][0] = s[i] == 'X' ? dp1[i][0] : (dp1[i][0] || check1[i - 1][0]);
//if (dp1[i][0])
// black[i - c[0] + 1] = max(black[i - c[0] + 1], c[0]);
}
for (int j = 1; j < k; j++) {
for (int i = c[j] + 2; i < n; i++) {
dp1[i][j] = pw[i] - pw[i - c[j]] == 0 && s[i - c[j]] != 'X' && check1[i - c[j] - 1][j - 1];
check1[i][j] = s[i] == 'X' ? dp1[i][j] : (dp1[i][j] || check1[i - 1][j]);
//if (dp1[i][j])
// black[i - c[j] + 1] = max(black[i - c[j] + 1], c[j]);
}
}
bool dp2[n][k] = {}, check2[n][k] = {};
for (int i = n - c[k - 1]; i >= 1; i--) {
dp2[i][k - 1] = pw[i + c[k - 1] - 1] - pw[i - 1] == 0 && pb[n - 1] - pb[i + c[k - 1] - 1] == 0;
check2[i][k - 1] = s[i] == 'X' ? dp2[i][k - 1] : (dp2[i][k - 1] || check2[i + 1][k - 1]);
//if (dp2[i][k - 1])
// black[i] = max(black[i], c[k - 1]);
}
for (int j = k - 2; j >= 0; j--) {
for (int i = n - c[j] - 2; i >= 1; i--) {
dp2[i][j] = pw[i + c[j] - 1] - pw[i - 1] == 0 && s[i + c[j]] != 'X' && check2[i + c[j] + 1][j + 1];
check2[i][j] = s[i] == 'X' ? dp2[i][j] : (dp2[i][j] || check2[i + 1][j]);
//if (dp2[i][j])
// black[i] = max(black[i], c[j]);
}
}
for (int i = 1; i < n; i++) {
if (dp2[i][0] && pb[i - 1] - pb[0] == 0)
black[i] = max(black[i], c[0]);
//if (dp1[i][k - 1] && pb[n - 1] - pb[i] == 0)
// black[i - c[k - 1] + 1] = max(black[i - c[k - 1] + 1], c[k - 1]);
}
for (int i = 2; i < n; i++) {
for (int j = 1; j < k; j++)
if (dp2[i][j] && check2[i - 2][j - 1])
black[i] = max(black[i], c[j]);
}
bool isBlack[n] = {}, isWhite[n] = {};
for (int i = 1, j = 0; i < n; i++) {
for (j = max(j, black[i]); i < n && j; j--, i++, j = max(j, black[i]))
isBlack[i] = true;
}
for (int i = 1; i < n; i++) {
if (s[i] == 'X')
continue;
isWhite[i] = s[i] == '_' || (check1[i - 1][k - 1] && pb[n - 1] - pb[i - 1] == 0) || (i != n - 1 && check2[i + 1][0] && pb[i] - pb[0] == 0);
for (int j = 0; j < k - 1; j++)
isWhite[i] = isWhite[i] || (check1[i - 1][j] && (i != n - 1 && check2[i + 1][j + 1]));
}
string ans = "";
for (int i = 1; i < n; i++) {
assert(isWhite[i] || isBlack[i]);
if (isWhite[i] && isBlack[i])
ans += '?';
else if (isWhite[i])
ans += '_';
else if (isBlack[i])
ans += 'X';
else
ans += '?';
}
return ans;
}
