#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN = 2e5+100;
ll a[MAXN];
ll k,n;
bool pf[101][MAXN],sf[101][MAXN];
ll cnt_white[MAXN];
ll black[MAXN],white[MAXN];
string solve_puzzle(string s, vector<int> c) {
k = sz(c);
n = sz(s);
c.insert(c.begin(),0);
for (ll i = 1;i <= n;i ++){
a[i] = s[i-1]=='X'?1:s[i-1]=='_'?0:-1;
cnt_white[i] = a[i] == 0;
cnt_white[i] += cnt_white[i-1];
}
pf[0][0] = 1;
for (ll i = 1;i <= n; i++){
if (a[i] == 1)break;
pf[0][i] = 1;
}
for (ll i = 1;i <= k;i ++){
for (ll j = c[i]+1;j <= n+1;j ++){
if (j <= n && a[j]==1)continue;
pf[i][j] = (cnt_white[j-1] - cnt_white[j-c[i]-1] > 0 ? 0 : pf[i-1][j-c[i]-1]) || pf[i][j-1];
}
}
for (ll i = n+1;i >= 0;i --){
if (a[i] == 1)break;
sf[k][i] = 1;
}
for (ll i = k - 1;i >= 0;i --){
for (ll j = n-c[i+1];j >= 0;j --){
if (j&&a[j]==1)continue;
sf[i][j] = (cnt_white[j+c[i+1]] - cnt_white[j] > 0 ? 0 : sf[i+1][j+c[i+1]+1]) || sf[i][j+1];
}
}
// for (ll i = 0;i <= k;i ++){
// for (ll j = 0;j <= n+1;j ++)cout<<pf[i][j]<<' ';
// cout<<'\n';
// }
// cout<<'\n';
// for (ll i = 0;i <= k;i ++){
// for (ll j = 0;j <= n+1;j ++)cout<<sf[i][j]<<' ';
// cout<<'\n';
// }
// cout<<pf[0][3]<<' '<<sf[0][3]<<'\n';
// cout<<pf[1][3]<<' '<<sf[1][3]<<'\n';
// cout<<pf[2][3]<<' '<<sf[2][3]<<'\n';
for (ll j = 0;j <= k;j ++){
for (ll i = 1;i <= n;i ++)white[i] |= pf[j][i] && sf[j][i];
if (j==0)continue;
for (ll i = 1;i + c[j] - 1 <= n;i ++){
if (pf[j-1][i-1] && sf[j][i+c[j]] && cnt_white[i+c[j]-1]-cnt_white[i-1] == 0){
black[i]++;
black[i+c[j]]--;
}
}
}
for (ll i = 1;i <= n;i ++)black[i] += black[i-1];
string ans;
ans.resize(n);
for (ll i = 0;i < n;i ++){
if (black[i+1] && white[i+1])ans[i] = '?';
else if (white[i+1])ans[i] = '_';
else ans[i] = 'X';
}
return ans;
}
