#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int n,k,dp[200001][101],dp2[200001][101],res[200001],a[200001],sum[200002],sum2[200002];
string c="._X?";
vector <int> v;
int f(int i, int j){
if (j<0)
return (i<0||!sum2[i]);
if (i<0)
return 0;
if (dp[i][j]!=-1)
return dp[i][j];
dp[i][j]=(a[i]==2?0:f(i-1,j));
if (j>=0)
if (i+1>=v[j])
if (i-v[j]<0||a[i-v[j]]!=2)
if (!(sum[i]-(i<v[j]?0:sum[i-v[j]])))
dp[i][j]|=f(i-v[j]-1,j-1);
return dp[i][j];
}
int g(int i, int j){
if (j>=k)
return (i>=n||sum2[n-1]==(i?sum2[i-1]:0));
if (i>=n)
return 0;
if (dp2[i][j]!=-1)
return dp2[i][j];
dp2[i][j]=(a[i]==2?0:g(i+1,j));
if (j<k)
if (n-i>=v[j])
if (i+v[j]>=n||a[i+v[j]]!=2)
if (!(sum[i+v[j]-1]-(i?sum[i-1]:0)))
dp2[i][j]|=g(i+v[j]+1,j+1);
return dp2[i][j];
}
string solve_puzzle(string s, vector <int> C){
n=s.length();
v=C;
k=v.size();
for (int i=0;i<n;i++)
if (s[i]=='_')
a[i]=1;
else if (s[i]=='X')
a[i]=2;
sum[0]=(a[0]==1);
sum2[0]=(a[0]==2);
for (int i=1;i<n;i++){
sum[i]=sum[i-1]+(a[i]==1);
sum2[i]=sum2[i-1]+(a[i]==2);
}
memset(dp,-1,sizeof(dp));
memset(dp2,-1,sizeof(dp2));
for (int i=0;i<k;i++)
for (int j=0;j+v[i]<=n;j++)
if ((!j||a[j-1]!=2)&&(j+v[i]==n||a[j+v[i]]!=2)&&!(sum[j+v[i]-1]-(j?sum[j-1]:0)))
if (f(j-2,i-1)&&g(j+v[i]+1,i+1)){
res[j]+=2;
res[j+v[i]]-=2;
}
for (int i=1;i<n;i++)
res[i]+=res[i-1];
for (int i=0;i<n;i++){
res[i]=min(res[i],2);
if (a[i])
res[i]=a[i];
else{
for (int j=0;j<=k;j++)
if (f(i-1,j-1)&&g(i+1,j)){
res[i]|=1;
break;
}
}
s[i]=c[res[i]];
}
return s;
}
