#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
const int mxN = 2e5+5;
const int mxK = 1e2+5;
int dp[mxN][mxK];
int N, K;
vector<int> C;
string S;
vector<int> W, B;
vector<int> pW;
int f(int n, int k){
if(n > N)return 0;
if(n == N)return k == K;
if(dp[n][k] != -1)return dp[n][k];
if(S[n] == 'X'){
if(k == K)return dp[n][k] = 0;
if(n+C[k] > N)return dp[n][k] = 0;
if(pW[n+C[k]-1] != (n ? pW[n-1] : 0))return dp[n][k] = 0;
int se;
if(n+C[k] == N)se = (k+1 == K);
else if(S[n+C[k]] == 'X')return dp[n][k] = 0;
else se = f(n+C[k]+1,k+1);
if(se){B[n] = max(B[n],C[k]);W[n+C[k]]=1;}
return dp[n][k] = se;
}
else if(S[n] == '_'){
W[n] = 1;
return dp[n][k] = f(n+1,k);
}
else{
int fi;
if(k == K)fi = 0;
else if(n+C[k] > N)fi = 0;
else if(pW[n+C[k]-1] != (n ? pW[n-1] : 0))fi = 0;
else if(n+C[k] == N)fi = (k+1 == K);
else if(S[n+C[k]] == 'X')fi = 0;
else fi = f(n+C[k]+1,k+1);
if(fi){B[n] = max(B[n],C[k]);W[n+C[k]]=1;}
int se = f(n+1,k);
W[n] |= se;
return dp[n][k] = fi|se;
}
}
string solve_puzzle(string s, vector<int> c) {
S = s;
C = c;
N = s.size();
K = c.size();
W.resize(N,0);
B.resize(N,0);
pW.resize(N,0);
for(int i = 0; i < N; ++i)pW[i] = (S[i] == '_') + (i ? pW[i-1] : 0);
for(int i = 0; i < mxN; ++i)for(int j = 0; j < mxK; ++j)dp[i][j] = -1;
f(0,0);
int cn = 0;
for(int i = 0; i < N; ++i){
cn = max(cn-1,B[i]);
if(W[i] && cn > 0)S[i] = '?';
else if(W[i])S[i] = '_';
else if(cn > 0)S[i] = 'X';
}
return S;
}
