#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, K = 1e2 + 10;
int ps[2][N],sp[2][N];
bool dp[N][K],pd[N][K];
int get(int c, int l, int r){
return ps[c][r]-ps[c][l-1];
}
string solve_puzzle(string s, vector<int> c) {
int n=s.size(),k=c.size();
s='#'+s;
c.insert(c.begin(),0);
for(int i=1; i<=n; i++){
ps[0][i]=ps[0][i-1];
ps[1][i]=ps[1][i-1];
if(s[i]=='_') ps[0][i]++;
if(s[i]=='X') ps[1][i]++;
}
dp[0][0]=1;
pd[n+1][k+1]=1;
for(int i=1; i<=n; i++){
if(s[i]=='X') continue;
for(int j=0; j<=k; j++){
dp[i][j]=dp[i-1][j];
if(j>0 && i>c[j] && get(0,i-c[j],i-1)==0) dp[i][j]|=dp[i-c[j]-1][j-1];
}
}
for(int i=n; i; i--){
if(s[i]=='X') continue;
for(int j=k+1; j; j--){
pd[i][j]=pd[i+1][j];
if(j<=k && n-i>=c[j] && get(0,i+1,i+c[j])==0) pd[i][j]|=pd[i+c[j]+1][j+1];
}
}
for(int i=1; i<=n; i++){
for(int j=0; j<=k; j++){
if(dp[i][j] && pd[i][j+1]) sp[0][i]=1;
if(!j) continue;
if(i>=c[j] && dp[i-c[j]][j-1] && pd[i+1][j+1] && get(0,i-c[j]+1,i)==0){
sp[1][i-c[j]+1]++;
sp[1][i+1]--;
}
}
}
string ans;
for(int i=1; i<=n; i++){
sp[1][i]+=sp[1][i-1];
if(sp[1][i] && sp[0][i]) ans.push_back('?');
else if(sp[1][i]) ans.push_back('X');
else ans.push_back('_');
}
return ans;
}
