//I love armpit fetish
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';
#define PR0(A, n) cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';
#define FILE_NAME "paint"
const int MAX_N = 200007;
const int MAX_K = 107;
int n, k, ps[MAX_N], prevWhite[MAX_N], nextWhite[MAX_N];
vector<int> c;
bool pf[MAX_K][MAX_N], sf[MAX_K][MAX_N], okWhite[MAX_N], okBlack[MAX_N];
string s;
void init() {
for (int i=1; i<=n; ++i) {
prevWhite[i] = (s[i]=='_' ? i : prevWhite[i-1]);
}
for (int i=n+1; i>=1; --i) {
nextWhite[i] = (s[i]=='_' ? i : nextWhite[i+1]);
}
}
void calc_prefix() {
pf[0][0] = true;
for (int i=0; i<=k; ++i) {
for (int j=1; j<=n; ++j) {
if (s[j]!='X')
pf[i][j] = pf[i][j-1];
if (s[j]!='_') {
int tmp = prevWhite[j];
if (j-tmp>=c[i] && s[j-c[i]]!='X') {
pf[i][j] = pf[i][j] || pf[i-1][max(0, j-c[i]-1)];
}
}
}
}
}
void calc_suffix() {
sf[k+1][n+1] = true;
for (int i=k+1; i>0; --i) {
for (int j=n; j>=1; --j) {
if (s[j]!='X')
sf[i][j] = sf[i][j+1];
if (s[j]!='_') {
int tmp = nextWhite[j];
if (tmp-j>=c[i] && s[j+c[i]]!='X') {
sf[i][j] = sf[i][j] || sf[i+1][min(n+1, j+c[i]+1)];
}
}
}
}
}
void checkWhiteSolution() {
for (int i=1; i<=n; ++i) {
if (s[i]=='X')
continue;
for (int j=0; j<=k; ++j) {
okWhite[i] = okWhite[i] || (pf[j][i-1] && sf[j+1][i+1]);
}
}
}
void checkBlackSolution() {
for (int i=1; i<=k; ++i) {
for (int j=1; j+c[i]-1<=n; ++j) {
if (nextWhite[j]>j+c[i]-1 && s[j-1]!='X'
&& s[j+c[i]]!='X' && pf[i-1][max(0, j-2)]
&& sf[i+1][min(n+1, j+c[i]+1)]) {
++ps[j]; --ps[j+c[i]];
}
}
}
for (int i=1; i<=n; ++i) {
ps[i] += ps[i-1];
if (ps[i])
okBlack[i] = true;
}
}
string solve_puzzle(string _s, vector<int> _c) {
n = _s.size();
s = '_' + _s + '_';
k = _c.size();
c = _c;
c.insert(c.begin(), 0);
c.push_back(0);
init();
calc_prefix();
calc_suffix();
checkWhiteSolution();
checkBlackSolution();
string res;
for (int i=1; i<=n; ++i) {
if (okWhite[i] && okBlack[i])
res += '?';
else if (okWhite[i])
res += '_';
else
res += 'X';
}
return res;
}
