#include "paint.h"
#include <cstdlib>
#include<bits/stdc++.h>
using namespace std;
int n,m;
int stat[200010];
int len[101]={};
bool all_front[200010][101],all_back[200010][101],one_front[200010][101],one_back[200010][101];
int streak_front[200010]={},streak_back[200010]={};
void solve_one_front(int x,int y)
{
if(!x && !y)
{
one_front[0][0]=true;
return;
}
if(!y)
{
one_front[x][0]=((one_front[x-1][0]) & (stat[x]!=1));
return;
}
if(streak_front[x]<len[y])
{
one_front[x][y]=false;
return;
}
if(x==len[y])
{
one_front[x][y]=(y==1);
return;
}
one_front[x][y]=((stat[x-len[y]]!=1) & all_front[x-len[y]-1][y-1]);
return;
}
void solve_front(int x,int y)
{
solve_one_front(x,y);
if(!x)
{
all_front[x][y]=(!y);
return;
}
if(stat[x]==2)
{
all_front[x][y]=all_front[x-1][y];
return;
}
if(stat[x]==1)
{
all_front[x][y]=one_front[x][y];
return;
}
all_front[x][y]=all_front[x-1][y] || one_front[x][y];
return;
}
void solve_one_back(int x,int y)
{
if((x==n+1) && (y==m+1))
{
one_back[n+1][m+1]=true;
return;
}
if(y==m+1)
{
one_back[x][y]=((one_back[x+1][y]) & (stat[x]!=1));
return;
}
if(streak_back[x]<len[y])
{
one_back[x][y]=false;
return;
}
if(n+1-x==len[y])
{
one_back[x][y]=(y==m);
return;
}
one_back[x][y]=((stat[x+len[y]]!=1) & all_back[x+len[y]+1][y+1]);
return;
}
void solve_back(int x,int y)
{
solve_one_back(x,y);
if(x==n+1)
{
all_back[x][y]=(y==m+1);
return;
}
if(stat[x]==2)
{
all_back[x][y]=all_back[x+1][y];
return;
}
if(stat[x]==1)
{
all_back[x][y]=one_back[x][y];
return;
}
all_back[x][y]=all_back[x+1][y] || one_back[x][y];
return;
}
int lp[200010];
bool test_white(int x)
{
if(stat[x]==2) return true;
if(stat[x]==1) return false;
for(int i=0;i<=m;i++) if(all_front[x-1][i] && all_back[x+1][i+1]) {return true;}
return false;
}
void longest_placed(int x)
{
if(x<=n && stat[x]==1) return;
if(x==n+1)
{
if(one_front[n][m]) lp[n+1]=len[m];
return;
}
for(int i=0;i<=m;i++)
{
if(one_front[x-1][i] && all_back[x+1][i+1])
{
lp[x]=max(lp[x],len[i]);
}
}
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
n=s.size();
m=c.size();
for(int i=0;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
all_front[i][j]=false;
all_back[i][j]=false;
one_front[i][j]=false;
one_back[i][j]=false;
}
}
for(int i=n;i>0;i--)
{
if(s[i-1]=='.') stat[i]=0;
else if(s[i-1]=='X') stat[i]=1;
else stat[i]=2;
}
for(int i=1;i<=n;i++)
{
streak_front[i]=(stat[i]!=2? streak_front[i-1]+1:0);
}
for(int i=n;i>=1;i--)
{
streak_back[i]=(stat[i]!=2? streak_back[i+1]+1:0);
}
for(int i=1;i<=m;i++)
{
len[i]=c[i-1];
}
for(int i=0;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
solve_front(i,j);
}
}
for(int i=n+1;i>=1;i--)
{
for(int j=m+1;j>=1;j--)
{
solve_back(i,j);
}
}
int res[200010]={};
int cou[200010]={};
for(int i=1;i<=n;i++)
{
if(test_white(i)) res[i]|=2;
}
for(int i=1;i<=n;i++) lp[i]=-1;
for(int i=1;i<=n+1;i++)
{
longest_placed(i);
if(lp[i]<0) continue;
cou[i]--;
cou[i-lp[i]]++;
}
for(int i=1;i<=n;i++)
{
cou[i]+=cou[i-1];
if(cou[i]) res[i]|=1;
}
string ss;
for(int i=1;i<=n;i++)
{
if(res[i]==1) ss.push_back('X');
else if(res[i]==2) ss.push_back('_');
else ss.push_back('?');
}
return ss;
}
