#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5,K=105;
int dp1[N][K],dp2[N][K],i,mx[N],ans[N][2],j,a[N],k,n;
string Ans;
#include <cstdlib>
std::string solve_puzzle(std::string s, std::vector<int> c) {
n=s.size()+1;
k=c.size();
s="##"+s;
s+="##";
for(i=1;i<=k;i++){
a[i]=c[i-1];
}
i=0;
while(i<=n && s[i]!='X') dp1[i][0]=1,i++;
i=n+2;
while(i>=0 && s[i]!='X') dp2[i][k+1]=1,i--;
for(i=2;i<=n;i++){
mx[i]=mx[i-1];
if(s[i]=='_') mx[i]=i;
for(j=1;j<=k;j++){
if(a[j]+1>i) break;
if(mx[i]<=i-a[j] && s[i-a[j]]!='X' && dp1[i-a[j]-1][j-1]){
dp1[i][j]=1;
}
if(s[i]!='X') dp1[i][j]=max(dp1[i-1][j],dp1[i][j]);
}
}
mx[n+1]=n+2;
for(i=n;i>=2;i--){
mx[i]=mx[i+1];
if(s[i]=='_') mx[i]=i;
for(j=k;j>=1;j--){
if(a[j]>n-i+1) break;
if(mx[i]>=i+a[j] && s[i+a[j]]!='X' && dp2[i+a[j]+1][j+1] ){
dp2[i][j]=1;
}
if(s[i]!='X') dp2[i][j]=max(dp2[i+1][j],dp2[i][j]);
}
}
i=0;
for(i=2;i<=n;i++){
for(j=1;j<=k+1;j++){
if(s[i]!='X')if(dp1[i-1][j-1] && dp2[i+1][j]){
ans[i-1][0]=1; //cout<<i<<endl;
}
if(s[i]!='_')
if(i+a[j]<=n+2 && dp2[i][j] && s[i-1]!='X' && dp1[i-2][j-1] && mx[i]>=i+a[j] && s[i+a[j]]!='X' && dp2[i+a[j]+1][j+1]){
ans[i-1][1]++;
ans[i+a[j]-1][1]--;//cout<<i<<"__"<<i+a[j]<<" "<<ans[i-1][1]<<endl;
}
}
}
for(i=1;i<n;i++){
ans[i][1]+=ans[i-1][1];
if(ans[i][0] && ans[i][1]) Ans+='?';
else if(ans[i][0]) Ans+='_';
else Ans+='X';
}
return Ans;
}
