#include "paint.h"
#include<bits/stdc++.h>
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;
}
set<int> val[k];
vector<int> tempval[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;
tempval[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(tempval[j-1].begin(),tempval[j-1].end(),lastbl);
if(low==tempval[j-1].end() || *low>=i-c[j])continue;
}
dp[i][j]=true;
val[j].I(i);tempval[j].PB(i);
}
}
set<int> bl,wh;
bool visited[n][k];memset(visited,false,sizeof(visited));
bool canbl[n],canwh[n];
memset(canbl,false,sizeof(canbl));memset(canwh,false,sizeof(canwh));
for(int i=0;i<n;i++){
if(s[i]=='.'){
bl.I(i);
wh.I(i);
}
}
queue<pair<int,int> > q;
for(int i=0;i<val[k-1].size();i++){
if(tempval[k-1][i]>=cb)q.P(MP(tempval[k-1][i],k-1));
}
if(!q.empty())for(int i=q.front().F+1;i<n;i++)canwh[i]=true;
while(!q.empty()){
pair<int,int> p=q.front();q.pop();
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+1);
if(by==bl.begin())bx=bl.end();
else{
by--;
if(*by<*bx)bx=bl.end();
}
auto x=bx;
while(true){
if(x==bl.end())break;
canbl[*x]=true;
if(x==by)break;
x++;
}
if(by!=bl.end())by++;
if(bx!=bl.end())bl.erase(bx,by);
if(p.S==0){
if(wh.empty())continue;
auto itr=wh.begin();
for(itr;itr!=wh.end();itr++){
if(*itr>=l)break;
canwh[*itr]=true;
}
wh.erase(wh.begin(),itr);
continue;
}
//Mark White
auto tpx=lower_bound(tempval[p.S-1].begin(),tempval[p.S-1].end(),lb[l]);
auto wx=upper_bound(wh.begin(),wh.end(),max(lb[l],*tpx));
auto wy=lower_bound(wh.begin(),wh.end(),l);
if(wy==wh.begin())wx=wh.end();
else{
wy--;
if(*wy<*wx)wx=wh.end();
}
auto y=wx;
while(true){
if(y==wh.end())break;
canwh[*y]=true;
if(y==wy)break;
y++;
}
if(wy!=wh.end())wy++;
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-1);
if(py==val[p.S-1].begin())px=val[p.S-1].end();
else{
py--;
if(*py<*px)px=val[p.S-1].end();
}
auto z=px;
while(true){
if(z==val[p.S-1].end())break;
if(visited[*z][p.S-1]==false){
q.P(MP(*z,p.S-1));
visited[*z][p.S-1]=true;
}
if(z==py)break;
z++;
}
if(py!=val[p.S-1].end())py++;
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;
}
