#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))
ll INF=1e18+10;
int inf=1e9+10;
ll M=1e9+7;
vii dp;
string s;
vi c;
int n,k;int m;
int solve(int a,int b){
if(dp[a][b]!=-1)return dp[a][b];
REP(i,0,c[b]){
if(a+i>=n)return dp[a][b]=0;
if(s[a+i]=='_')return dp[a][b]=0;
}
if(a+c[b]<n&&s[a+c[b]]=='X')return dp[a][b]=0;
if(b==k-1&&a+c[b]<=m)return dp[a][b]=0;
if(b==k-1)return dp[a][b]=1;
dp[a][b]=0;
REP(i,a+c[b]+1,n){
dp[a][b]|=solve(i,b+1);
if(s[i]=='X')break;
}
return dp[a][b];
}
std::string solve_puzzle(std::string s1, std::vector<int> c1) {
s=s1;
c=c1;
k=c.size();
n=s.size();
dp.resize(n,vi(k,-1));
REP(i,0,n)if(s[i]=='X')m=i;
REP(i,0,n){
solve(i,0);
if(s[i]=='X')break;
}
string ans;
ans.resize(n,'_');
REP(i,0,n)if(s[i]=='X')ans[i]='X';
for(int i=k-1;i>=0;i--){
vi p;
REP(j,0,n)if(dp[j][i]>0)p.PB(j);
if(p.empty())continue;
REP(j,p.back(),p[0]+c[i])ans[j]='X';
for(auto u:p){
REP(j,u,u+c[i])if(ans[j]!='X')ans[j]='?';
}
}
return ans;
}
