#include <bits/stdc++.h>
#include "paint.h"
#define inf 1000000007
#define mod 1000000007
// #define int long long
// #pragma GCC optimize("Ofast","inline","-ffast-math")
// #pragma GCC target("avx,sse2,sse3,sse4,mmx")
using namespace std;
template <typename T> void read(T &x){
x=0;char ch=getchar();int fh=1;
while (ch<'0'||ch>'9'){if (ch=='-')fh=-1;ch=getchar();}
while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
x*=fh;
}
template <typename T> void write(T x) {
if (x<0) x=-x,putchar('-');
if (x>9) write(x/10);
putchar(x%10+'0');
}
template <typename T> void writeln(T x) {
write(x);
puts("");
}
int n,k;
char s[300005];
int c[105];
int sumb[200005],sumw[200005];
bool dpf[105][200005],dpb[105][200005];
bool canb[200005],canw[200005],canst[200005];
bool check(int l,int r,int op)
{
if(l<1||r>n) return false;
if(op!=1&&l-1>=1&&s[l-1]=='X') return false;
if(op!=0&&r+1<=n&&s[r+1]=='X') return false;
if(sumw[r]-sumw[l-1]>0) return false;
return true;
}
string solve_puzzle(string S,vector<int> C)
{
n=S.size(),k=C.size();
for(int i=1;i<=n;++i) s[i]=S[i-1];
for(int i=1;i<=k;++i) c[i]=C[i-1];
for(int i=1;i<=n;++i) sumb[i]=sumb[i-1]+(s[i]=='X'),sumw[i]=sumw[i-1]+(s[i]=='_');
for(int i=0;i<=k;++i)
for(int j=0;j<=n;++j)
{
if(!i) dpf[i][j]=(!sumb[j]);
else if(!j) dpf[i][j]=0;
else if(s[j]=='_') dpf[i][j]=dpf[i][j-1];
else if(s[j]=='X') dpf[i][j]=(check(j-c[i]+1,j,0)&&dpf[i-1][max(0,j-c[i]-1)]);
else dpf[i][j]=(dpf[i][j-1]||(check(j-c[i]+1,j,0)&&dpf[i-1][max(0,j-c[i]-1)]));
}
for(int i=k+1;i>=1;--i)
for(int j=n+1;j>=1;--j)
{
if(i==k+1) dpb[i][j]=(!(sumb[n]-sumb[j-1]));
else if(j==n+1) dpb[i][j]=0;
else if(s[j]=='_') dpb[i][j]=dpb[i][j+1];
else if(s[j]=='X') dpb[i][j]=(check(j,j+c[i]-1,1)&&dpb[i+1][min(n+1,j+c[i]+1)]);
else dpb[i][j]=(dpb[i][j+1]||(check(j,j+c[i]-1,1)&&dpb[i+1][min(n+1,j+c[i]+1)]));
}
for(int i=1;i<=n;++i)
{
if(s[i]=='X') continue;
for(int j=0;j<=k;++j)
canw[i]|=(dpf[j][i-1]&&dpb[j+1][i+1]);
}
for(int i=1;i<=k;++i)
{
for(int j=1;j<=n;++j)
canst[j]=(check(j,j+c[i]-1,2)&&dpf[i-1][max(0,j-2)]&&dpb[i+1][min(n+1,j+c[i]+1)]);
int cur=0;
for(int j=1;j<=n;++j)
{
cur+=canst[j];if(j-c[i]>=1) cur-=canst[j-c[i]];
canb[j]|=(cur>0);
}
}
string ans;
for(int i=1;i<=n;++i)
if(canb[i]&&canw[i]) ans+="?";
else if(canb[i]) ans+="X";
else ans+="_";
return ans;
}
