#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pf printf
#define pb push_back
#define all(x) x.begin(),x.end()
#define lb(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define ub(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define INF 1023456789
typedef pair<int,int> ii;
#define maxk 105
#define maxn 200005
int far[maxn],pfx[maxk][maxn],sfx[maxk][maxn];
vector<ii> black,white;
inline bool canblack(int l,int r){
int i=lb(black,ii(l,INF));
if(i==0)return false;
return r<=black[i-1].se;
}
inline bool canwhite(int l,int r){
int i=lb(white,ii(l,INF));
if(i==0)return false;
return r<=white[i-1].se;
}
string solve_puzzle(string s,vector<int> c){
int n=s.length(),k=c.size();
string ans(n,'.');
int l=-1,r=-1;
for(int i=0;i<n;++i){
if(s[i]=='_'){
if(r!=-1)black.pb({l+1,r+1});
l=r=-1;
}
else{
if(l==-1)l=r=i;
else r=i;
}
}
if(r!=-1)black.pb({l+1,r+1});
l=r=-1;
for(int i=0;i<n;++i){
if(s[i]=='X'){
if(r!=-1)white.pb({l+1,r+1});
l=r=-1;
}
else{
if(l==-1)l=r=i;
else r=i;
}
}
if(r!=-1)white.pb({l+1,r+1});
pfx[0][0]=1;
for(int i=1;i<=n;++i){
if(s[i-1]=='X')break;
pfx[0][i]=1;
}
for(int i=1;i<=k;++i){
for(int j=1;j<=n;++j){
if(s[j-1]!='X')pfx[i][j]|=pfx[i][j-1];//can be white
if(s[j-1]!='_'){//can be black
if(j-c[i-1]<0)continue;
if(j-c[i-1]!=0&&s[j-c[i-1]-1]=='X')continue;//j-c[i] is white
if(!canblack(j-c[i-1]+1,j))continue;//[j-c[i]+1,j] can black
if(i==k&&j+c[i-1]<=n&&!canwhite(j+c[i-1],n))continue;
if(i!=1||j-c[i-1]!=0)pfx[i][j]|=pfx[i-1][j-c[i-1]-1];
else pfx[i][j]=1;
}
}
}
sfx[k+1][n+2]=sfx[k+1][n+1]=1;
for(int i=n;i>=1;--i){
if(s[i-1]=='X')break;
sfx[k+1][i]=1;
}
for(int i=k;i>=1;--i){
for(int j=n;j>=1;--j){
if(s[j-1]!='X')sfx[i][j]|=sfx[i][j+1];//can be white
if(s[j-1]!='_'){//can be black
if(j+c[i-1]-1>n)continue;
if(j+c[i-1]-1!=n&&s[j+c[i-1]-1]=='X')continue;//j+c[i] is white
if(!canblack(j,j+c[i-1]-1))continue;//[j,j+c[i]-1] can black
if(i==1&&j!=1&&!canwhite(1,j-1))continue;
sfx[i][j]|=sfx[i+1][j+c[i-1]+1];
}
}
}
for(int j=1;j<=n;++j){
if(s[j-1]=='X')continue;
for(int i=0;i<=k;++i){
if(pfx[i][j-1]&&sfx[i+1][j+1])ans[j-1]='_';
}
}
int far=0;
for(int j=1;j<=n;++j){
for(int i=1;i<=k;++i){
if(!(i==1&&j==1)&&(j==1||s[j-2]=='X'))continue;
if(j+c[i-1]<=n&&s[j+c[i-1]-1]=='X')continue;
if(j+c[i-1]-1>n||!canblack(j,j+c[i-1]-1))continue;
if(((i==1&&j==1)||pfx[i-1][j-2])&&sfx[i+1][j+c[i-1]+1]){
int l=far,r=j+c[i-1]-1;
for(int i=l+1;i<=r;++i){
if(ans[i-1]=='_')ans[i-1]='?';
else if(ans[i-1]=='.')ans[i-1]='X';
}
far=r;
}
}
far=max(far,j);
}
return ans;
}
