#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pii pair<int,int>
#define pll pair<long long,long long>
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define pb push_back
#define sz(x) (int)(x).size()
#define rsz resize
#define ass assign
#define F(i,l,r) for(int i=(l);i<(r);++i)
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
template<typename T> using pqg = priority_queue<T, vector<T>, greater<T>>;
#define each(a,x) for(auto a:x)
#define FOR(i,a) for(int i=0;i<(a);i++)
#define ROF(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define eb emplace_back
#define ft front()
#define V vector
#include "paint.h"
string solve_puzzle(string s,V<int> c){
int n=sz(s),k=sz(c);
V<V<bool>> L(n+2,V<bool>(k+1,0)),R(n+2,V<bool>(k+1,0));
auto can_fit_black=[&](int st,int len){
if(st<0 || st+len>n)return 0;
F(i,st,st+len){
if(s[i]=='_')return 0;
}
return 1;
};
L[0][0]=1;
FOR(j,k+1){
FOR(i,n+1){
if(!L[i][j])continue;
if(i<n && s[i]!='X')L[i+1][j]=1;
if(j<k){
int len=c[j];
if(can_fit_black(i,len)){
if(i+len==n){
if(j==k-1)L[n][k]=1;
}else if(i+len<n && s[i+len]!='X')L[i+len+1][j+1]=1;
}
}
}
}
R[n][k]=1;
ROF(j,0,k+1){
ROF(i,0,n+1){
if(!R[i][j])continue;
if(i && s[i-1]!='X')R[i-1][j]=1;
if(j){
int len=c[j-1],st=i=len;
if(can_fit_black(i,len)){
if(!st){
if(j==1)R[0][0]=1;
}else if(st && s[st-1]!='X')R[st-1][j-1]=1;
}
}
}
}
V<bool> can_white(n,0),can_black(n,0);
V<int> bdiff(n+1,0);
FOR(i,n){
FOR(j,k+1){
if(L[i][j] && R[i+1][j]){
if(s[i]!='X')can_white[i]=1;
}
}
}
FOR(j,k){
int len=c[j];
FOR(p,n-len+1){
bool ps=L[p][j],suff=(p+len==n)?(j==k-1):R[p+len+1][j+1];
bool range=can_fit_black(p,len),space=(p+len==n) || (s[p+len]!='X');
if(ps && suff && range && space){
bdiff[p]++;
bdiff[p+len]--;
}
}
}
int cur=0;
string res="";
FOR(i,n){
cur+=bdiff[i];
if(cur)can_black[i]=1;
if(can_black[i] && can_white[i])res+='?';
else if(can_white[i])res+='X';
else res+='_';
}
return res;
}
