#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
string solve_puzzle(string s,vector<int> c) {
int N=s.size(),K=c.size();
s.insert(s.begin(),'.');
c.insert(c.begin(),0);
// pf/sf
vector<int> pfb(N+2,0),pfw(N+2,0);
for(int i=1;i<=N;++i) {
pfb[i]=pfb[i-1]+(s[i]=='X');
pfw[i]=pfw[i-1]+(s[i]=='_');
}
// dp
vector<vector<int>> pfdp(N+3,vector<int>(K+3,0)),sfdp(N+3,vector<int>(K+3,0));
for(int i=0;i<=N;++i) {
for(int j=0;j<=K;++j) {
if(!j) {
pfdp[i][j]=!pfb[i];
continue;
}
if(c[j]>i) {
pfdp[i][j]=0;
continue;
}
bool fb,fw;
if(s[i-c[j]]=='X'||(pfw[i]-pfw[i-c[j]])) fb=0;
else fb=pfdp[max(0,i-c[j]-(j>1))][j-1];
fw=pfdp[i-1][j];
if(s[i]=='X') pfdp[i][j]=fb;
else if(s[i]=='_') pfdp[i][j]=fw;
else pfdp[i][j]=fb||fw;
}
}
for(int i=N+1;i>0;--i) {
for(int j=K+1;j>0;--j) {
if(j==K+1) {
sfdp[i][j]=!(pfb[N]-pfb[i-1]);
continue;
}
if(c[j]>N-i+1) {
sfdp[i][j]=0;
continue;
}
bool fb,fw;
if(s[i+c[j]]=='X'||(pfw[i+c[j]-1]-pfw[i-1])) fb=0;
else fb=sfdp[min(N+1,i+c[j]+(j<K))][j+1];
fw=sfdp[i+1][j];
if(s[i]=='X') sfdp[i][j]=fb;
else if(s[i]=='_') sfdp[i][j]=fw;
else sfdp[i][j]=fb||fw;
}
}
vector<bool> b(N+2),w(N+2);
// can be white?
for(int i=1;i<=N;++i) {
if(s[i]=='_') w[i]=1;
else if(s[i]=='X') w[i]=0;
else for(int j=0;j<=K;++j) if(pfdp[i-1][j]&&sfdp[i+1][j+1]) w[i]=1;
}
// can be black
vector<int> diff(N+2);
for(int i=1;i<=K;++i) {
for(int j=1;j+c[i]-1<=N;++j) {
bool v=1;
if(s[j-1]=='X'||s[j+c[i]]=='X') v=0;
if(pfw[j+c[i]-1]-pfw[j-1]) v=0;
if(!pfdp[max(0,j-2)][i-1]||!sfdp[min(N+1,j+c[i]+1)][i+1]) v=0;
if(v) {
++diff[j];
--diff[j+c[i]];
}
}
}
int sum=0;
for(int i=1;i<=N;++i) {
sum+=diff[i];
b[i]=sum>0;
}
string ans="";
for(int i=1;i<=N;++i) {
if(w[i]&&b[i]) ans.push_back('?');
else if(w[i]) ans.push_back('_');
else if(b[i]) ans.push_back('X');
}
return ans;
}
