#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N ((int)201*1000)
#define K ((int)101)
int n,k;
int lft_[N],rght_[N];
bool dpl[N][K],dpr[N][K];
string solve_puzzle(string s, vector<int> c)
{
n=s.size();k=c.size();
s='.'+s+'.';
lft_[0]=0;
for(int i=1;i<=n;i++)
lft_[i]=max(lft_[i-1],(s[i]=='_'?i:0));
rght_[n+1]=n+1;
for(int i=n;i>=1;i--)
rght_[i]=min(rght_[i+1],(s[i]=='_'?i:n+1));
dpl[0][0]=dpr[n+1][k+1]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=k;j++)
{
if(s[i]!='X' && dpl[i-1][j]){dpl[i][j]=1;continue;}
if(!j || i<c[j-1] || lft_[i]>=i-c[j-1]+1 || s[i-c[j-1]]=='X')continue;
// if(i==6 && j==2)cout<<"hir\n";
dpl[i][j]=((i-c[j-1]-1)>=0)?dpl[i-c[j-1]-1][j-1]:(j==1);
}
for(int i=n;i>=1;i--)
for(int j=1;j<=k+1;j++)
{
if(s[i]!='X' && dpr[i+1][j]){dpr[i][j]=1;continue;}
if(j==k+1 || n-i+1<c[j-1] || rght_[i]<=i+c[j-1]-1 || s[i+c[j-1]]=='X')continue;
dpr[i][j]=((i+c[j-1]+1)<=n+1)?dpr[i+c[j-1]+1][j+1]:(j==k);
}
string ans="";
for(int i=1;i<=n;i++)
{
if(s[i]!='.'){ans+=s[i];continue;}
int res=0;
for(int j=0;j<=k;j++)
if(dpl[i-1][j] && dpr[i+1][j+1])
{
res=1;
break;
}
for(int j=1;j<=k;j++)
{
int l=max(i-c[j-1]+1,lft_[i]+1),r=l+c[j-1]-1;
while(l<=i)
{
if(r>n || rght_[i]<=r)break;
if(l<1 || s[l-1]=='X' || s[r+1]=='X' || (l-2<0 && j!=1) || (r+2>n+1 && j!=k)){l++;r++;continue;}
if((l-2<0 || dpl[l-2][j-1]) && (r+2>n+1 || dpr[r+2][j+1])){res|=2;break;}
l++;r++;
}
// if(i==4)cout<<j<<" "<<l<<" "<<r<<" "<<dpl[l-2][j-1]<<" "<<dpr[r+2][j+1]<<"\n";
if(res>=2)break;
}
if(res==1)ans+='_';
if(res==2)ans+='X';
if(res==3)ans+='?';
}
return ans;
}
