#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
bitset<200100> tran1[101],tran2,ok[101],ok2[101],wht;
int sumblk[200100],prfblk[200100],prfwht[200100],n_;
inline int nowht(int l,int r){
return r<=n_&&prfwht[r]==prfwht[l-1];
}
inline int noblk(int l,int r){
return prfblk[r]==prfblk[l-1];
}
string solve_puzzle(string s, vector<int> c) {
int n=s.size(),k=c.size();
n_=n;
s=" "+s;
for(int i=1;i<=n;i++)
prfblk[i]=s[i]=='X',prfwht[i]=s[i]=='_';
for(int i=1;i<=n;i++)
prfblk[i]+=prfblk[i-01],prfwht[i]+=prfwht[i-1];
for(int i=1;i<=n;i++){
for(int j=0;j<k;j++)
tran1[j][i]=nowht(i,i+c[j]-1)&&noblk(i+c[j],i+c[j]);
tran2[i]=noblk(i,i);
}
ok[0][1]=1;
for(int i=1;i<=n;i++) {
if(tran2[i])for(int j=0;j<=k;j++)
ok[j][i+1]=ok[j][i+1]|ok[j][i];
for(int j=0;j<k;j++)if(tran1[j][i]&&ok[j][i])
ok[j+1][i+c[j]+1]=1;
}
ok2[k][n+1]=1;
ok2[k][n+2]=1;
for(int i=n+1;--i;){
if(tran2[i])for(int j=0;j<=k;j++)
ok2[j][i]=ok2[j][i+1]|ok2[j][i];
for(int j=0;j<k;j++)
if(tran1[j][i]&&ok2[j+1][i+c[j]+1])
ok2[j][i]=1;
}
for(int i=0;i<=k;i++)
ok[i]&=ok2[i];
for(int i=1;i<=n;i++){
for(int j=0;j<k;j++){
if(!ok[j][i])continue;
if(tran2[i]&&ok[j][i+1])wht[i]=1;
if(tran1[j][i]&&ok[j+1][i+c[j]+1])
sumblk[i]++,sumblk[i+c[j]]--,wht[i+c[j]]=1;
}
}
string str;
for(int i=1;i<=n;i++){
sumblk[i]+=sumblk[i-1];
if(wht[i]&&sumblk[i])
str+='?';
else if(sumblk[i])
str+='X';
else str+='_';
}
return str;
}
