#include "paint.h"
#include<bits/stdc++.h>
#include <cstdlib>
using namespace std;
const int N=2e5+10;
bool pre[N][210],suf[N][210];
int b[N],w[N],f[N];
bool cb[N],cw[N];
std::string solve_puzzle(std::string s, std::vector<int> c) {
string uwu;
int n=s.size(),k=c.size();
c.insert(c.begin(),0);
s=" "+s;
for(int i=1;i<=n;i++){
if(s[i]=='_') w[i]++;
if(s[i]=='X') b[i]++;
w[i]+=w[i-1];
b[i]+=b[i-1];
}
pre[0][0]=1;
for(int i=1;i<=n;i++) pre[i][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
if(s[i]!='X') pre[i][j]|=pre[i-1][j];
//if(i==3 && j==1) cout<<i-c[j] <<" " <<w[i]-w[i-c[j]] <<"\n";
if(i==c[j] && w[c[j]]==0){
pre[i][j]|=pre[0][j-1];
}
if(i-c[j]-1>=0 && s[i-c[j]]!='X' && w[i]-w[i-c[j]]==0){
pre[i][j]|=pre[i-c[j]-1][j-1];
}
}
}
suf[n+1][k+1]=1;
for(int i=n;i>=1;i--){
for(int j=1;j<=k;j++){
if(s[i]!='X') suf[i][j]|=suf[i+1][j];
if(i+c[j]==n+1 && w[n]-w[i-1]==0) suf[i][j]|=suf[n+1][j+1];
if(i+c[j]<=n && s[i+c[j]]!='X' && w[i+c[j]-1]-w[i-1]==0){
suf[i][j]|=suf[i+c[j]+1][j+1];
}
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
if((j==0 || pre[i-1][j]) && (j==k || suf[i+1][j+1])){
cw[i]=1;
}
}
}
for(int i=1;i<=k;i++){
//trying all possible figure of c[i] and finding intersect which will be position of black
//due to guaranteed that puzzle is solvable, there will be at least one segment which satiefied
for(int j=c[i];j<=n;j++){
bool ok=true;
if(pre[j][i] && suf[j-c[i]+1][i] && w[j]-w[j-c[i]]==0){
f[j-c[i]+1]++,f[j+1]--;
}
}
}
for(int i=1;i<=n;i++){
f[i]+=f[i-1];
if(f[i]) cb[i]=1;
}
string ret;
for(int i=1;i<=n;i++){
if(cb[i] && cw[i]) ret.push_back('?');
else if(cb[i]) ret.push_back('X');
else ret.push_back('_');
}
return ret;
}
