#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;
bool check(vi v){
int n = v.size(); int cnt = 0; f0r(i,n)if(v[i]==1)cnt++;
if(cnt==0){
vi w; int cur = 0; f0r(i,n){
if(v[i]==-1)cur++; else{
if(cur>0)w.pb(cur); cur = 0;
}
}
if(cur>0)w.pb(cur); cur = 0;
int ptr = 0; f0r(i,w.size()){
int d = w[i]; int sum = -1; while(ptr < c.size() && c[ptr] + 1 + sum <= d)sum+=c[ptr]+1,ptr++;
}
if(ptr == c.size())return 1; else return 0;
}
else{
vi prev, aft; pii dur = {-1,-1}; int cur = 0, has = 0, pos = 0; f0r(i,n){
if(v[i]==-1)cur++;
else if(v[i]==1){
pos = cur, cur++, has = 1;
}
else{
if(has)dur = mp(cur, pos);
else{
if(dur.first==-1){
if(cur>0)prev.pb(cur);
}
else{
if(cur>0)aft.pb(cur);
}
}
has = 0, cur = 0;
}
}
if(has)dur = mp(cur, pos);
else{
if(dur.first==-1){
if(cur>0)prev.pb(cur);
}
else{
if(cur>0)aft.pb(cur);
}
}
// vout(v);
// vout(prev);
// dout2(dur.first,dur.second);
// vout(aft);
int ptr = 0; f0r(i,prev.size()){
int d = prev[i]; int sum = -1; while(ptr < c.size() && c[ptr] + 1 + sum <= d)sum+=c[ptr]+1,ptr++;
}
if(ptr == c.size())ptr--;
while(ptr >= 0 && c[ptr] > dur.first)ptr--;
if(ptr==-1)return 0;
vi idk; f0r(i,c[ptr])idk.pb(1); ptr++; while(ptr < c.size()){
if(idk.size() + c[ptr] + 1 <= dur.first){
idk.pb(0); f0r(i,c[ptr])idk.pb(1); ptr++;
}
else break;
}
if(idk.size()==dur.first && idk[dur.second]==0)ptr--;
f0r(i,aft.size()){
int d = aft[i]; int sum = -1; while(ptr < c.size() && c[ptr] + 1 + sum <= d)sum+=c[ptr]+1,ptr++;
}
if(ptr==c.size())return 1; else 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;
}
