#include "paint.h"
#include<bits/stdc++.h>
#define int long long
#define f0r(i,n) for(int i = 0; i < n; i++)
#define FOR(i,k,n) for(int i = k; i < n; i++)
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define vi vector<int>
#define pii pair<int,int>
#define dout(x); cout<<x<<' '<<#x<<endl;
#define dout2(x,y); cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<endl;
#define vout(v); for(auto u : v)cout<<u<<' '; cout<<endl;
using namespace std;
vi c;
int g(int l, int r, vi &ps){
return ps[r+1] - ps[l];
}
bool check(vi v){
int n = v.size(), k = c.size(); int cnt = 0; f0r(i,n)if(v[i]==1)cnt++;
vi ps0(n+1); FOR(i,1,n+1)ps0[i]=ps0[i-1]+(v[i-1]==0);
vi ps1(n+1); FOR(i,1,n+1)ps1[i]=ps1[i-1]+(v[i-1]==1);
vector<vector<bool>> dp(n, vector<bool>(k,0)); f0r(i,n){
if(i+1>=c[0] && g(i-c[0]+1,i,ps0)==0){
if(ps1[i-c[0]+1]==0){
dp[i][0]=1;
}
}
FOR(j,1,k){
if(i-c[j]+1>=2 && g(i-c[j]+1,i,ps0) == 0){
if(v[i-c[j]] != 1){
int ptr = i-c[j]-1; while(ptr >= 0){
if(v[ptr+1]==1)break;
if(dp[ptr][j-1]){
dp[i][j] = 1; break;
}
ptr--;
}
}
}
}
}
// if(v[4]==1){
// // dout(dp[n-1][k-1]);
// f0r(i,n)cout<<dp[i][0]<<' '; cout<<'\n';
// }
if(dp[n-1][k-1])return 1;
f0r(i,n-1)if(dp[i][k-1]&&g(i+1,n-1,ps1)==0)return 1;
return 0;
}
std::string solve_puzzle(std::string s, std::vector<signed> C) {
int n = s.size(); int m = C.size(); for(auto u : C)c.pb(u); string ans = s; vector<vector<bool>>can(n, vector<bool>(2));
vi v; f0r(i,n)if(s[i]=='X')v.pb(1); else if(s[i] == '_')v.pb(0); else v.pb(-1);
f0r(i,n)if(v[i]==-1){
f0r(j,2){
vi w = v; w[i] = j;
if(check(w))can[i][j]=1;
}
}
// f0r(i,n){
// f0r(j,2)cout<<can[i][j]<<' '; cout<<'\n';
// }
f0r(i,n)if(v[i]==-1){
if(can[i][0]&&can[i][1])ans[i]='?'; else if(can[i][0])ans[i]='_'; else ans[i]='X';
}
return ans;
}
