#include "paint.h"
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
#include <cstdlib>
ll n,k,i,p1[201010],p2[201010],C[110],j,mas[201010],kel[201010],hv;
char A[201010];
string S;
bool b1[110][201010],b2[110][201010],d1[110][201010],d2[110][201010];
bool depe1(ll aa,ll bb)
{
if(aa==0)
{
if(bb<=0||p2[bb]==0)
return 1;
else
return 0;
}
else
if(!b1[aa][bb])
{
b1[aa][bb]=1;
if(bb-C[aa]<0)
d1[aa][bb]=0;
else
{
if(A[bb]=='X')
{
if(p1[bb]-p1[bb-C[aa]]==0&&A[bb-C[aa]]!='X')
d1[aa][bb]=depe1(aa-1,bb-C[aa]-1);
else
d1[aa][bb]=0;
}
else
{
if(p1[bb]-p1[bb-C[aa]]==0&&A[bb-C[aa]]!='X')
d1[aa][bb]=depe1(aa-1,bb-C[aa]-1);
d1[aa][bb]=d1[aa][bb]|depe1(aa,bb-1);
}
}
}
return d1[aa][bb];
}
bool depe2(ll aa,ll bb)
{
if(aa>=k+1)
{
if(bb>n||p2[n]-p2[bb-1]==0)
return 1;
else
return 0;
}
else
if(!b2[aa][bb])
{
b2[aa][bb]=1;
if(bb+C[aa]-1>n)
d2[aa][bb]=0;
else
{
if(A[bb]=='X')
{
if(p1[bb+C[aa]-1]-p1[bb-1]==0&&A[bb+C[aa]]!='X')
d2[aa][bb]=depe2(aa+1,bb+C[aa]+1);
else
d2[aa][bb]=0;
}
else
{
if(p1[bb+C[aa]-1]-p1[bb-1]==0&&A[bb+C[aa]]!='X')
d2[aa][bb]=depe2(aa+1,bb+C[aa]+1);
d2[aa][bb]=d2[aa][bb]|depe2(aa,bb+1);
}
}
}
return d2[aa][bb];
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
n=s.length();
k=c.size();
for(i=1;i<=n;i++)
{
A[i]=s[i-1];
p1[i]=p1[i-1];
p2[i]=p2[i-1];
if(A[i]=='_')
p1[i]++;
if(A[i]=='X')
p2[i]++;
}
for(i=1;i<=k;i++)
C[i]=c[i-1];
for(i=1;i<=k;i++)
{
for(j=1;j+C[i]-1<=n;j++)
{
//cout<<i<<" "<<j<<" "<<j+C[i]-1<<" "<<depe1(i-1,j-2)<<" "<<depe2(i+1,j+C[i]+1)<<"\n";
if(p1[j+C[i]-1]-p1[j-1]==0&&depe1(i-1,j-2)&&depe2(i+1,j+C[i]+1)&&(A[j-1]!='X')&&(A[j+C[i]]!='X'))
{
//cout<<i<<" "<<j<<" "<<j+C[i]-1<<"\n";
mas[j]++;
kel[j+C[i]-1]++;
}
}
}
for(i=0;i<n;i++)
S+=".";
for(i=1;i<=n;i++)
{
hv+=mas[i];
if(hv)
S[i-1]='X';
hv-=kel[i];
}
//return S;
for(i=0;i<=k;i++)
{
for(j=1;j<=n;j++)
{
if(A[j]!='X'&&depe1(i,j-1)&&depe2(i+1,j+1))
{
// cout<<i<<" "<<j<<"\n";
if(S[j-1]=='X')
S[j-1]='?';
else
if(S[j-1]=='.')
S[j-1]='_';
}
}
}
return S;
}
