#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
const ll INF=1LL<<60;
string to_string(string s){
return s;
}
string to_string(char c){
string ret="";
ret+=c;
return ret;
}
template<class S,class T>
string to_string(pair<S,T> x){
string ret="("+to_string(x.first)+","+to_string(x.second)+")";
return ret;
}
template<class S>
string to_string(S x){
string ret="{";
bool flg=0;
for(auto i:x){
if(flg)ret+=",";
ret+=to_string(i);
flg=1;
}
ret+="}";
return ret;
}
void debug(){
cerr<<"\n";
}
template<class S,class... T>
void debug(S x,T... y){
cerr<<to_string(x)<<" ";
debug(y...);
}
//#define DEBUG
#ifdef DEBUG
#define DBG(x...) cerr<<"DBG:";debug(x)
#else
#define DBG(x...)
#endif
std::string solve_puzzle(std::string s, std::vector<int> c) {
string fin=s;
s="_"+s+"_";
DBG(s,c);
int n=s.size();
int m=c.size();
vector<vector<int>> dp1(n,vector<int>(m+1,0));
vector<vector<int>> dp2(n,vector<int>(m+1,0));
rep(r,2){
vector<int> cum(n+1,0);
rep(i,n){
cum[i+1]=cum[i];
if(s[i]=='_')cum[i+1]++;
}
vector<vector<int>> dp(n,vector<int>(m+1,0));
dp[0][0]=1;
rep(i,n-1){
rep(j,m+1){
if(!dp[i][j])continue;
if(s[i+1]!='X'){
dp[i+1][j]=1;
}
if(j==m)continue;
if(i+c[j]+1<n&&s[i+c[j]+1]!='X'){
if(cum[i+c[j]+1]-cum[i+1]==0){
dp[i+c[j]+1][j+1]=1;
}
}
}
}
if(r==0)dp1=dp;
else dp2=dp;
reverse(all(s));
reverse(all(c));
}
vector<int> cum(n+1,0);
rep(i,n){
cum[i+1]=cum[i];
if(s[i]=='_')cum[i+1]++;
}
reverse(all(dp2));
DBG(dp1,dp2);
vector<int> ans(n,0);
vector<vector<int>> dp(n,vector<int>(m+1,0));
dp[0][0]=1;
rep(i,n-1){
rep(j,m+1){
if(!dp[i][j])continue;
if(s[i+1]!='X'){
dp[i+1][j]=1;
}
if(j==m)continue;
if(i+c[j]+1<n&&s[i+c[j]+1]!='X'){
if(cum[i+c[j]+1]-cum[i+1]==0){
dp[i+c[j]+1][j+1]=1;
if(dp2[i+c[j]+1][m-(j+1)]){
ans[i+1]++;
ans[i+c[j]+1]--;
}
}
}
}
}
rep(i,n-1){
ans[i+1]+=ans[i];
}
vector<int> white(n);
rep(i,n){
rep(j,m+1){
if(dp1[i][j]&&dp2[i][m-j]){
white[i]=1;
}
}
}
rep(i,n-2){
if(ans[i+1]&&white[i+1]){
fin[i]='?';
}
else if(ans[i+1]){
fin[i]='X';
}
else{
fin[i]='_';
}
}
return fin;
}
