#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int a[200010],b[200010],cnt[200010][3],n,m;
int mem[200010][201];
int mx[200010],my[200010];
int solve(int n,int k) {
if(!n) return !k;
if(mem[n][k]!=-1) return mem[n][k];
int& r=mem[n][k];
if(a[n]==2) r=solve(n-1,k);
else if(a[n]==1) {
if(!k||n<b[k]) r=0;
else if(cnt[n][2]-cnt[n-b[k]][2]>0) r=0;
else if(n>b[k]&&a[n-b[k]]==1) r=0;
else {
if(n==b[k]) r=solve(0,k-1);
else r=solve(n-b[k]-1,k-1);
if(r) mx[n-b[k]+1]++,mx[n+1]--,my[n-b[k]]=1;
}
} else {
r=solve(n-1,k);
if(r) my[n]=1;
if(!k||n<b[k]);
else if(cnt[n][2]-cnt[n-b[k]][2]>0);
else if(n>b[k]&&a[n-b[k]]==1);
else {
int t=0;
if(n==b[k]) t=solve(0,k-1);
else t=solve(n-b[k]-1,k-1);
//printf("n:%d,k:%d,t:%d\n",n,k,t);
if(t) {
mx[n-b[k]+1]++,mx[n+1]--;
my[n-b[k]]=1;
}
r|=t;
}
}
return r;
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
n=s.length(); m=c.size();
int i,j;
memset(mem,-1,sizeof(mem));
for(i=0;i<n;i++) {
if(s[i]=='X') a[i+1]=1;
else if(s[i]=='_') a[i+1]=2;
for(j=0;j<3;j++)cnt[i+1][j]=cnt[i][j];
cnt[i+1][a[i+1]]++;
}
for(i=0;i<m;i++) b[i+1]=c[i];
solve(n,m);
string ret="";
for(i=1;i<=n;i++) {
mx[i]+=mx[i-1];
if(mx[i]>0&&my[i]>0) ret+="?";
else if(mx[i]>0) ret+="X";
else ret+="_";
}
return ret;
}
