#include "paint.h"
#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_multiset;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define pll pair<ll, ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
string solve_puzzle(string s, vector<int> c) {
ll n = s.length(), m = c.size();
bool dp[m+1][n+1], dp2[m+1][n+1], tm;
ll pf[n+1], pf2[n+1];
pf[0] = pf2[0] = 0;
iloop(0, n) {
pf[i+1] = pf[i] + (s[i] == 'X');
pf2[i+1] = pf2[i] + (s[i] == '_');
}
iloop(0, m+1) jloop(0, n+1) {
if (!i) {dp[i][j] = (pf[j] == 0); continue;}
if (!j) {dp[i][j] = 0; continue;};
dp[i][j] = 0;
if (s[j-1] != '_') {
tm = 1;
if (j < c[i-1]) tm = 0;
else if (pf2[j] != pf2[j - c[i-1]]) tm = 0;
else if (j > c[i-1] && s[j - c[i-1] - 1] == 'X') tm = 0;
else if (j > c[i-1] && !dp[i-1][j - c[i-1] - 1]) tm = 0;
else if (j == c[i-1] && i != 1) tm = 0;
dp[i][j] |= tm;
}
if (s[j-1] != 'X') dp[i][j] |= dp[i][j-1];
}
iloop(0, m+1) jloop(0, n+1) {
if (!i) {dp2[i][j] = (pf[n-j] == pf[n]); continue;}
if (!j) {dp2[i][j] = 0; continue;};
dp2[i][j] = 0;
if (s[n-j] != '_') {
tm = 1;
if (j < c[m-i]) tm = 0;
else if (pf2[n-j] != pf2[n - j + c[m-i]]) tm = 0;
else if (j > c[m-i] && s[n - j + c[m-i]] == 'X') tm = 0;
else if (j > c[m-i] && !dp2[i-1][j - c[m-i]]) tm = 0;
else if (j == c[m-i] && i != 1) tm = 0;
dp2[i][j] |= tm;
}
if (s[n-j] != 'X') dp2[i][j] |= dp2[i][j-1];
}
bool can[n][2];
memset(can, 0, sizeof(can));
iloop(0, n) if (s[i] != 'X') {
jloop(0, m+1) can[i][0] |= dp[j][i] & dp2[m-j][n-i-1];
}
iloop(0, m) {
ll ps = 0;
jloop(0, n+1-c[i]) {
if (pf2[j+c[i]] != pf2[j]) continue;
if (j && s[j-1] == 'X') continue;
if (j+c[i] < n && s[j+c[i]] == 'X') continue;
if (j == 0 && i != 0) continue;
if (j >= 1 && !dp[i][j-1]) continue;
if (j == n-c[i] && i != m-1) continue;
if (j < n-c[i] && !dp2[m-i-1][n-c[i]-j-1]) continue;
kloop(max(ps, (ll)j), j + c[i]) can[k][1] = 1;
ps = j + c[i];
}
}
string res;
iloop(0, n) {
if (can[i][0] && can[i][1]) res += '?';
else if (can[i][0]) res += '_';
else res += 'X';
}
return res;
}
