#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << " "
#define nl cout << "\n"
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MAXK = 100+10;
const int MAXN = 2e5+100;
int N, K, a[MAXN], pr1[MAXN], pr2[MAXN], memo[MAXK][MAXN];
vector<int> c;
bool only_black(int l, int r){
if(r >= N) return false;
return (pr2[r + 1] - pr2[l] == (r - l + 1));
/*
rep(i, l, r + 1){
if(a[i] == 0) return false;
}
return true;
*/
}
bool only_white(int l, int r){
return ((pr1[r + 1] - pr1[l]) == 0);
/*
rep(i, l, r + 1){
if(a[i] == 1) return false;
}
return true;
*/
}
bool col[2][MAXN];
int cnt[2][MAXN];
void setrange(int l, int r, int k){
if(l > r) return;
r = min(r, N - 1);
if(k != 0 && k != 1) return;
/*
rep(i, l, r + 1){
col[k][i] = true;
}
*/
cnt[k][l]++;
cnt[k][r + 1]--;
}
void get(){
int cur[] = {0, 0};
rep(i, 0, N){
cur[0] += cnt[0][i];
cur[1] += cnt[1][i];
if(cur[0] > 0) col[0][i] = true;
if(cur[1] > 0) col[1][i] = true;
}
}
int f(int i, int k){
if(i >= N){
if(k == K) return 1;
return 0;
}
if(k == K){
if(only_white(i, N - 1)){
setrange(i, N - 1, 0);
return 1;
}
return 0;
}
int& ans = memo[k][i];
if(ans != -1){
return ans;
}
ans = 0;
if(a[i] == 0){
ans = f(i + 1, k);
if(ans == 1){
setrange(i, i, 0);
}
} else if(a[i] == 1){
int j = i + c[k];
if(only_black(i, j - 1) && (j == N || a[j] != 1)){
ans = f(j + 1, k + 1);
if(ans == 1){
setrange(i, j - 1, 1);
setrange(j, j, 0);
}
}
} else{
ans = f(i + 1, k);
if(ans == 1){
setrange(i, i, 0);
}
int j = i + c[k];
if(only_black(i, j - 1) && (j == N || a[j] != 1)){
int ans2 = f(j + 1, k + 1);
if(ans2 == 1){
setrange(i, j - 1, 1);
setrange(j, j, 0);
ans = ans2;
}
}
}
return ans;
}
string solve_puzzle(string S, vector<int> C){
N = SZ(S), K = SZ(C); c = C;
rep(i, 0, N){
if(S[i] == '_') a[i] = 0;
else if(S[i] == 'X') a[i] = 1;
else a[i] = -1;
}
rep(i, 0, N){
pr1[i + 1] += pr1[i];
pr2[i + 1] += pr2[i];
if(a[i] >= 0) pr1[i + 1] += a[i], pr2[i + 1] += a[i];
else pr1[i + 1] += 0, pr2[i + 1] += 1;
}
memset(memo, -1, sizeof(memo));
memset(col, false, sizeof(col));
f(0, 0);
get();
string answer = "";
rep(i, 0, N){
if(col[0][i] && col[1][i]){
answer += '?';
} else if(col[0][i]){
answer += '_';
} else if(col[1][i]){
answer += 'X';
} else assert(false);
}
return answer;
}
