#include "paint.h"
#include<bits/stdc++.h>
#include <cstdlib>
using namespace std;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define P push
#define I insert
string solve_puzzle(string s, vector<int> c) {
int n=s.size(),k=c.size();
bool dp[n][k];memset(dp,false,sizeof(dp));
int lb[n],lw[n];
int cb=-1,cw=-1;
for(int i=0;i<n;i++){
lb[i]=cb;lw[i]=cw;
if(s[i]=='X')cb=i;
if(s[i]=='_')cw=i;
}
vector<int> val[k];
for(int i=0;i<n;i++){
for(int j=0;j<k;j++){
if(s[i]=='_' || i-c[j]<-1)continue;
if(i-c[j]==-1){
if(lw[i]<=i-c[j] && j==0){
dp[i][j]=true;
val[j].PB(i);
}
continue;
}
if(lw[i]>i-c[j])continue;
int lastbl=lb[i-c[j]+1];
if(j==0 && lastbl!=-1)continue;
if(j>0){
auto low=lower_bound(val[j-1].begin(),val[j-1].end(),lastbl);
if(low==val[j-1].end() || *low>=i-c[j])continue;
}
dp[i][j]=true;
val[j].PB(i);
}
}
queue<pair<int,int> > q;
for(int i=0;i<val[k-1].size();i++){
if(val[k-1][i]>cb)break;
q.P(MP(val[k-1][i],k-1));
}
set<int> bl,wh;
for(int i=0;i<n;i++){
if(s[i]=='.'){
bl.I(i);
wh.I(i);
}
}
bool canbl[n],canwh[n];
memset(canbl,false,sizeof(canbl));memset(canwh,false,sizeof(canwh));
while(!q.empty()){
pair<int,int> p=q.front();q.pop();
if(p.S==0)continue;
int l=p.F-c[p.S]+1;int r=p.F;
//Mark Black
auto bx=lower_bound(bl.begin(),bl.end(),l);
auto by=lower_bound(bl.begin(),bl.end(),r);
auto x=bx;
while(true){
if(x==bl.end())break;
canbl[*x]=true;
if(x==by)break;
x++;
}
if(bx!=bl.end())bl.erase(bx,by);
//Mark White
auto wx=upper_bound(wh.begin(),wh.end(),lb[l]);
auto wy=lower_bound(wh.begin(),wh.end(),l-1);
auto y=wx;
while(true){
if(y==wh.end())break;
canwh[*y]=true;
if(y==wy)break;
y++;
}
if(wx!=wh.end())wh.erase(wx,wy);
//Find next
auto px=lower_bound(val[p.S-1].begin(),val[p.S-1].end(),lb[l]);
auto py=lower_bound(val[p.S-1].begin(),val[p.S-1].end(),l-2);
auto z=px;
while(true){
if(z==val[p.S-1].end())break;
q.P(MP(*z,p.S-1));
if(z==py)break;
z++;
}
if(px!=val[p.S-1].end())val[p.S-1].erase(px,py);
}
for(int i=0;i<n;i++){
if(s[i]=='.'){
if(canbl[i] && canwh[i])s[i]='?';
else if(canbl[i])s[i]='X';
else s[i]='_';
}
}
return s;
}
