#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],z[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++){
if(s[i]=='X') break;
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 && 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--){
if(s[i]=='X') break;
suf[i][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(pre[i-1][j] && suf[i+1][j+1] && b[i]-b[i-1]==0){
cw[i]=1;
}
}
}
for(int i=1;i<=k;i++){
// cout<<"i" <<i <<"\n";
// for(int j=1;j<=n;j++) cout<<pre[j][i] <<" ";
// cout<<"\n";
// for(int j=1;j<=n;j++) cout<<suf[j][i] <<" ";
// cout<<"\n";
//cout<<i <<"\n";
int l=INT_MIN,r=INT_MAX;
for(int j=c[i];j<=n;j++){
bool ok=true;
//check if able to place on c[i] on [j-c[i]+1,j]
int pr=j,pl=j-c[i]+1;
bool cf=1,cs=1;
if(pl==1){
if(i-1==0) cf=1;
else cf=0;
}
else{
if(s[pl-1]!='X') cf=pre[pl-2][i-1];
else cf=0;
}
if(pr==n){
if(i==k) cs=1;
else cs=0;
}
else{
if(s[pr+1]!='X') cs=suf[pr+2][i+1];
else cs=0;
}
if(w[pr]-w[pl-1]==0 && cf && cs){
f[pl]++,f[pr+1]--;
l=max(l,pl);
r=min(r,pr);
//cout<<pl <<" " <<pr <<"\n";
}
}
//cout<<c[i] <<" " <<l <<" " <<r <<"\n";
if(l<=r) z[l]++,z[r+1]--;
}
for(int i=1;i<=n;i++){
f[i]+=f[i-1];
z[i]+=z[i-1];
if(f[i]) cb[i]=1;
if(z[i]) cw[i]=0;
}
string ret;
for(int i=1;i<=n;i++){
if(s[i]!='.'){
ret.push_back(s[i]);
continue;
}
if(cb[i] && cw[i]) ret.push_back('?');
else if(cb[i]) ret.push_back('X');
else ret.push_back('_');
}
return ret;
}
