#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int n, k;
int brw[200005];
bool pos_le[200005][105];
bool pos_ri[200005][105];
int posB[200005];
bool posW[200005];
std::string solve_puzzle(std::string s, std::vector<int> c)
{
s='_'+s+'_';
n=s.size();
for(int i=0; i<n; i++)
{
if(i) brw[i]=brw[i-1];
if(s[i]=='_') brw[i]++;
}
k=c.size();
for(int j=0; j<=n; j++)
{
if(s[j]=='X') break;
pos_le[j][k]=1;
}
pos_ri[n][k]=1;
for(int j=n-1; j>=0; j--)
{
if(s[j]=='X') break;
pos_ri[j][k]=1;
}
for(int i=0; i<k; i++)
{
for(int j=1; j+c[i]<n; j++)
{
if(i && !pos_le[j-1][i-1]) continue;
if(!i && !pos_le[j-1][k]) continue;
if(brw[j+c[i]-1]-brw[j-1]) continue;
if(s[j+c[i]]=='X') continue;
pos_le[j+c[i]][i]=1;
for(int t=j+c[i]+1; t<n && s[t]!='X'; t++, j++) pos_le[t][i]=1;
}
}
for(int i=k-1; i>=0; i--)
{
for(int j=n-c[i]-1; j>=1; j--)
{
if(!pos_ri[j+c[i]][i+1]) continue;
if(brw[j+c[i]-1]-brw[j-1]) continue;
if(s[j-1]=='X') continue;
pos_ri[j-1][i]=1;
for(int t=j-2; t>=0 && s[t]!='X'; t--, j--) pos_ri[t][i]=1;
}
}
for(int i=0; i<k; i++)
{
for(int j=1; j+c[i]<n; j++)
{
if(brw[j+c[i]-1]-brw[j-1]) continue;
if(i==0 && !pos_le[j-1][k]) continue;
if(i && !pos_le[j-1][i-1]) continue;
if(!pos_ri[j+c[i]][i+1]) continue;
posB[j]++;
posB[j+c[i]]--;
}
}
for(int j=1; j<=n; j++)
{
for(int i=0; i<=k; i++)
{
if(i && pos_le[j][i-1] && pos_ri[j][i]) posW[j]=1;
if(!i && pos_le[j][k] && pos_ri[j][i]) posW[j]=1;
}
}
for(int j=1; j<=n; j++)
{
posB[j]+=posB[j-1];
if(posB[j] && posW[j]) s[j]='?';
else if(posB[j]) s[j]='X';
else if(posW[j]) s[j]='_';
}
return s.substr(1, n-2);
}
