#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef short int si;
typedef vector<si> vsi;
typedef vector<vsi> vvsi;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)
bool poss(int i, int ci, const string& s, const vi& c, const vi& prev_x, const vi& prev_u, vvb& dp, vvb& dpvis, vpi& poss_u, vpi& poss_x) {
if(i >= -2 && ci == -1) {
if(i < 0 || prev_x[i] == -1) {
if(i >= 0) poss_u.pb({0, i});
return true;
} else return false;
}
if(i < 0) return false;
if(ci != -1 && c[ci] > i + 1) return false;
if(!dpvis[i][ci]) {
bool poss_cur_u = s[i] != 'X' && poss(i - 1, ci, s, c, prev_x, prev_u, dp, dpvis, poss_u, poss_x);
if(poss_cur_u) poss_u.pb({i, i});
// Recursive case: current is x
bool poss_cur_x = (i - c[ci] < 0 || s[i - c[ci]] != 'X') && prev_u[i] <= i - c[ci] && poss(i - c[ci] - 1, ci - 1, s, c, prev_x, prev_u, dp, dpvis, poss_u, poss_x);
if(poss_cur_x) {
if(i - c[ci] >= 0) poss_u.pb({i - c[ci], i - c[ci]});
poss_x.pb({max(i - c[ci] + 1, 0), i});
}
dp[i][ci] = poss_cur_u || poss_cur_x;
dpvis[i][ci] = true;
}
return dp[i][ci];
}
string solve_puzzle(string s, vi c) {
int n = s.size();
int k = c.size();
vvb dp;
vvb dpvis;
for(int i = 0; i < n; i++) {
vb dpr(k, false);
vb dpvisr(k, false);
dp.pb(dpr);
dpvis.pb(dpvisr);
}
vi prev_u(n, -1);
vi prev_x(n, -1);
for(int i = 0; i < n; i++) {
if(i > 0) {
prev_u[i] = prev_u[i - 1];
prev_x[i] = prev_x[i - 1];
}
if(s[i] == '_') prev_u[i] = i;
if(s[i] == 'X') prev_x[i] = i;
}
vpi poss_u;
vpi poss_x;
vi c_pref(n, 0);
for(int i = 0; i < k; i++) {
if(i == 0) c_pref[i] = c[i];
else c_pref[i] = c_pref[i - 1] + c[i] + 1;
}
for(int i = 0; i < n; i++) {
for(int ci = 0; ci < k; ci++) {
if(i < c_pref[i] - 3) continue;
poss(i, ci, s, c, prev_x, prev_u, dp, dpvis, poss_u, poss_x);
}
}
poss(n - 1, k - 1, s, c, prev_x, prev_u, dp, dpvis, poss_u, poss_x);
vi u_pref(n + 1, 0);
vi x_pref(n + 1, 0);
for(pi inds: poss_u) {
u_pref[inds.fi]++;
u_pref[inds.se + 1]--;
}
for(pi inds: poss_x) {
x_pref[inds.fi]++;
x_pref[inds.se + 1]--;
}
int us = 0;
int xs = 0;
string ans;
for(int i = 0; i < n; i++) {
us += u_pref[i];
xs += x_pref[i];
if(us > 0 && xs > 0) ans.pb('?');
else if(us > 0) ans.pb('_');
else ans.pb('X');
}
return ans;
}
