#include "paint.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
string s;
std::string solve_puzzle(std::string _s, std::vector<int> c) {
swap(s,_s);
int n=sz(s);
int k=sz(c);
vector<bool> black(n,false);
vector<bool> white(n,false);
vector<int> pref(n,0);
for (int i = 0; i < n; i++)
{
if(s[i]=='_') white[i]=true, pref[i]++;
else if(s[i]=='X') black[i]=true;
if(i>0) pref[i]+=pref[i-1];
}
vector<vector<bool>> dp(n,vector<bool>(k+1,false));
vector<vector<bool>> dp2(n,vector<bool>(k+1,false));
for (int _ = 0; _ < 2; _++)
{
if(s[0]!='X') dp[0][0]=true;
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= k; j++)
{
if(i>0&&s[i]!='X') dp[i][j]=dp[i-1][j]|dp[i][j];
int sm=pref[i];
if(j>0&&i-c[j-1]>=0) sm-=pref[i-c[j-1]];
if(j>0&&i>c[j-1]&&s[i-c[j-1]]!='X'&&sm==0) dp[i][j]=(dp[i-c[j-1]-1][j-1])|dp[i][j];
if(j==1&&i==c[j-1]&&sm==0&&s[i-c[j-1]]!='X') dp[i][j]=true;
if(j==1&&i+1==c[j-1]&&sm==0) dp[i][j]=true;
}
}
swap(dp,dp2);
reverse(all(s));
reverse(all(c));
for (int i = 0; i < n; i++)
{
if(s[i]=='_') pref[i]=1;
else pref[i]=0;
if(i>0) pref[i]+=pref[i-1];
}
}
for (int i = 0; i < n; i++) reverse(all(dp2[i]));
reverse(all(dp2));
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= k; j++)
{
bool lft=((i==0&&j==0)||(i>0&&dp[i-1][j]));
bool rgt=((i==n-1&&j==k)||(i<n-1&&dp2[i+1][j]));
if(lft&&rgt&&s[i]!='X') white[i]=true;
}
}
/*for (int i = 0; i < n; i++)
{
for (int j = 0; j < k; j++)
{
for (int l = i-c[j]+1; l <= i; l++)
{
int r=l+c[j]-1;
if(l<0||r>=n) continue;
bool lft=((l==0&&j==0)||(((l==1&&j==0)||(l>1&&dp[l-2][j]))&&s[l-1]!='X'));
bool rgt=((r==n-1&&j==k-1)||(((r==n-2&&j==k-1)||(r<n-2&&dp2[r+2][j+1]))&&s[r+1]!='X'));
int sm=pref[r];
if(l>0) sm-=pref[l-1];
if(lft&&rgt&&sm==0) black[i]=true;
}
}
}*/
vector<pair<int,int>> blck;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < k; j++)
{
int l=i;
int r=l+c[j]-1;
if(l<0||r>=n) continue;
bool lft=((l==0&&j==0)||(((l==1&&j==0)||(l>1&&dp[l-2][j]))&&s[l-1]!='X'));
bool rgt=((r==n-1&&j==k-1)||(((r==n-2&&j==k-1)||(r<n-2&&dp2[r+2][j+1]))&&s[r+1]!='X'));
int sm=pref[r];
if(l>0) sm-=pref[l-1];
if(lft&&rgt&&sm==0) blck.push_back({l,r});
}
}
sort(all(blck));
int mx=-1;
int _i=0;
for (int i = 0; i < n; i++)
{
while(_i<sz(blck)&&blck[_i].first==i){
mx=max(mx, blck[_i].second);
_i++;
}
if(mx>=i) black[i]=true;
}
string out(n,'*');
for (int i = 0; i < n; i++)
{
if(white[i]&&black[i]) out[i]='?';
else if(white[i]) out[i]='_';
else if(black[i]) out[i]='X';
}
return out;
}
