// #include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int sum(int l, int r, vector<int>& p) {
l = max(0, l);
r = min(r, (int)p.size() - 1);
if(l > r) return 0;
return p[r] - (l > 0 ? p[l - 1] : 0);
}
std::string solve_puzzle(std::string s, std::vector<int> a) {
int n = s.size(), m = a.size();
a.insert(a.begin(), 0);
s = "@" + s + "@";
vector<vector<vector<int>>>dp(2, vector<vector<int>>(n + 2, vector<int>(m + 2, 0)));
vector<int>p(n + 2);
for(int i = 1; i <= n; ++i) {
p[i] = p[i - 1] + (s[i] == '_');
}
for(int i = 0; i <= n + 1; ++i) {
if(s[i] == 'X') break;
dp[0][i][0] = 1;
}
for(int i = n + 1; i >= 0; --i) {
if(s[i] == 'X') break;
dp[1][i][m + 1] = 1;
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
int start = i - a[j] + 1;
if(s[i] != 'X') {
dp[0][i][j] |= dp[0][i - 1][j];
}
if(s[i] != '_' && start >= 1 && sum(start, i, p) == 0) {
if(start == 1) {
dp[0][i][j] |= (j == 1);
} else if(s[start - 1] != 'X') {
dp[0][i][j] |= dp[0][start - 2][j - 1];
}
}
}
}
for(int i = n; i >= 1; --i) {
for(int j = m; j >= 1; --j) {
int end = i + a[j] - 1;
if(s[i] != 'X') {
dp[1][i][j] |= dp[1][i + 1][j];
}
if(s[i] != '_' && end <= n && sum(i, end, p) == 0) {
if(end == n) {
dp[1][i][j] |= (j == m);
} else if(s[end + 1] != 'X') {
dp[1][i][j] |= dp[1][end + 2][j + 1];
}
}
}
}
vector<bool> can_white(n + 2), can_black(n + 2);
vector<int> pref(n + 2);
for(int i = 1; i <= n; ++i) {
if(s[i] == 'X') continue;
for(int j = 0; j <= m; ++j) {
bool check_left = 0, check_right = 0;
check_left = dp[0][i - 1][j];
check_right = dp[1][i + 1][j + 1];
if(check_left && check_right) {
can_white[i] = true;
}
}
}
for(int i = 1; i <= n; ++i) {
if(s[i] == '_') continue;
for(int j = 1; j <= m; ++j) {
int start = i - a[j] + 1;
if(start <= 0) continue;
if(start > 1 && s[start - 1] == 'X') continue;
bool check_left = 0, check_right = 0, check_me = 0;
if(start - 2 < 0) {
if(j == 1) check_left = 1;
} else {
check_left = dp[0][start - 2][j - 1] && (s[start - 1] != 'X');
}
if(i + 2 > n + 1) {
if(j == m) check_right = 1;
} else {
check_right = dp[1][i + 2][j + 1] && (s[i + 1] != 'X');
}
if(sum(start, i, p) == 0) {
check_me = 1;
}
if(check_left && check_me && check_right) {
++pref[start];
--pref[i + 1];
}
}
}
for(int i = 1; i <= n; ++i) {
pref[i] += pref[i - 1];
can_black[i] = pref[i] > 0;
}
string answer = "";
for(int i = 1; i <= n; ++i) {
if(can_white[i] && can_black[i]) {
answer += '?';
} else {
if(can_white[i]) {
answer += '_';
} else {
answer += 'X';
}
}
}
return answer;
}
