#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 vvi vector<vi>
#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; vvi ps;
int g(int l, int r, int d){
return ps[d][r+1] - ps[d][l];
}
std::string solve_puzzle(std::string s, std::vector<signed> C) {
int n = s.size(); int k = C.size(); for(auto u : C)c.pb(u); string ans = s; vector<vector<int>>can(n, vector<int>(2));
vi v; f0r(i,n)if(s[i]=='X')v.pb(1); else if(s[i] == '_')v.pb(0); else v.pb(-1);
ps.resize(2); f0r(i,2)ps[i].resize(n+1); FOR(i,1,n+1)f0r(j,2)ps[j][i] = ps[j][i-1] + (v[i-1] == j);
vector<vector<int>> dp(n+1, vector<int>(k+1)), rdp(n+1, vector<int>(k+1));
int has = 0; dp[0][0] = 1; FOR(i,1,n+1){if(v[i-1]==1)has=1; if(!has)dp[i][0]=1;}
FOR(i,1,n+1)FOR(j,1,k+1){
if(v[i-1]==0||v[i-1]==-1)dp[i][j] |= dp[i-1][j];
if(v[i-1]==1||v[i-1]==-1)dp[i][j] |= (i-c[j-1] >= 0 && g(i-c[j-1],i-1,0)==0 && (i-c[j-1]==0||v[i-c[j-1]-1]!=1) &&
((i-c[j-1]-1>=0 && dp[i-c[j-1]-1][j-1]) || (j==1 && i-c[j-1] == 0)));
}
reverse(v.begin(),v.end()); reverse(c.begin(),c.end());
has = 0; rdp[0][0] = 1; FOR(i,1,n+1){if(v[i-1]==1)has=1; if(!has)rdp[i][0]=1;}
FOR(i,1,n+1)FOR(j,1,k+1){
if(v[i-1]==0||v[i-1]==-1)rdp[i][j] |= rdp[i-1][j];
if(v[i-1]==1||v[i-1]==-1)rdp[i][j] |= (i-c[j-1] >= 0 && g(i-c[j-1],i-1,0)==0 && (i-c[j-1]==0||v[i-c[j-1]-1]!=1) &&
((i-c[j-1]-1>=0 && rdp[i-c[j-1]-1][j-1]) || (j==1 && i-c[j-1] == 0)));
}
reverse(v.begin(),v.end()); reverse(c.begin(),c.end());
f0r(i,n)if(v[i]==-1){
f0r(j,k+1)can[i][0] |= (dp[i][j] && rdp[n-i-1][k-j]);
}
f0r(i,k){
vector<bool> cn(n);
for(int j = 0; j + c[i] - 1 < n; j++){
cn[j] = (g(j,j+c[i]-1,0)==0 && (j==0||v[j-1]!=1) && (j+c[i]==n||v[j+c[i]]!=1) &&
((j>0 && dp[j-1][i]) || (j==0&&i==0)) &&
((n-j-c[i]-1>=0&&rdp[n-j-c[i]-1][k-i-1]) || (n-j-c[i]-1==-1 && i==k-1)));
}
// vout(cn);
vi cf(n+1); f0r(j,n)if(cn[j])cf[j]++,cf[j+c[i]]--;
int cur = 0; f0r(j,n){
cur += cf[j]; if(cur > 0)can[j][1]=1;
}
}
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;
}
