#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool dpl[200200][101], dpr[200200][101];
int S[200200], N, K;
string solve_puzzle(string str, vector<int> a) {
string ans;
N = str.size(), K = a.size();
ans.resize(str.size());
str.insert(str.begin(), 0);
str.push_back(0);
a.insert(a.begin(), 0);
for (int i=1;i<=N;i++) S[i] = S[i-1] + (str[i]=='_');
for (int i=0;i<=N;i++){
if (str[i]=='X') break;
dpl[i][0] = 1;
}
for (int i=N+1;i;i--){
if (str[i]=='X') break;
dpr[i][K+1] = 1;
}
for (int j=1;j<=K;j++){
for (int i=1;i<=N;i++){
if (i<a[j]) continue;
if (S[i]-S[i-a[j]]==0){
bool tmp = (j==1);
if (i-a[j]-1>=0) tmp = dpl[i-a[j]-1][j-1];
if (str[i+1]!='X' && str[i-a[j]]!='X') dpl[i][j] |= tmp;
}
if (str[i]!='X') dpl[i][j] |= dpl[i-1][j];
}
}
for (int j=K;j;j--){
for (int i=N;i;i--){
if (N+1-i<a[j]) continue;
if (S[i+a[j]-1]-S[i-1]==0){
bool tmp = (j==K);
if (i+a[j]+1<=N+1) tmp = dpr[i+a[j]+1][j+1];
if (str[i+a[j]]!='X' && str[i-1]!='X') dpr[i][j] |= tmp;
}
if (str[i]!='X') dpr[i][j] |= dpr[i+1][j];
}
}
/*for (int j=0;j<=K+1;j++){
for (int i=0;i<=N+1;i++) printf("%d", dpl[i][j]);
printf("\n");
}
printf("\n");
for (int j=0;j<=K+1;j++){
for (int i=0;i<=N+1;i++) printf("%d", dpr[i][j]);
printf("\n");
}*/
for (int j=1;j<=K;j++){
int prv = -1e9;
for (int i=1;i<=N;i++){
if (i+a[j]>N+1) break;
if (S[i+a[j]-1]-S[i-1]==0){
if (str[i+a[j]]!='X' && str[i-1]!='X'){
bool tmp1 = (j==1), tmp2 = (j==K);
if (i-2>=0) tmp1 = dpl[i-2][j-1];
if (i+a[j]+1<=N+1) tmp2 = dpr[i+a[j]+1][j+1];
if (tmp1 && tmp2){
for (int k=max(prv+a[j], i);k<i+a[j];k++)ans[k-1] = 'X';
prv = i;
}
}
}
}
}
for (int i=1;i<=N;i++){
for (int j=0;j<=K;j++) if (str[i]!='X' && dpl[i-1][j] && dpr[i+1][j+1]){
if (ans[i-1]=='X' || ans[i-1]=='?') ans[i-1] = '?';
else ans[i-1] = '_';
}
}
for (int i=0;i<N;i++) assert(ans[i]);
return ans;
}
