#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
using ll = long long;
using pii = pair<int,int> ;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;
const int INF =(1<<30)-1;
std::string solve_puzzle(std::string s, std::vector<int> c) {
int n = s.size(), k = c.size();
vector<pii> nextblank(n,{-1,n}), nextfull(n,{-INF,INF});
int lastb = -1, lastf = -INF;
for(int i = 0; i < n; i++){
if(s[i] == '_')
lastb = i;
else if(s[i] == 'X')
lastf = i;
nextblank[i].ff = lastb;
nextfull[i].ff = lastf;
}
lastb = n;
lastf = INF;
for(int i = n-1; i >= 0; i--){
if(s[i] == '_')
lastb = i;
else if(s[i] == 'X')
lastf = i;
nextblank[i].ss = lastb;
nextfull[i].ss = lastf;
}
matrix<int> canpref(k,vector<int>(n)), cansuf(k,vector<int>(n));
for(int i = 0; i < n; i++){
if(nextblank[i].ff <= i-c[0]){
canpref[0][i] = 1;
}
if(s[i]!='X' && i){
canpref[0][i]|=canpref[0][i-1];
}
}
for(int i = n-1; i >= 0; i--){
if(nextblank[i].ss >= i+c[k-1]){
cansuf[k-1][i] = 1;
}
if(s[i]!='X' && i != n-1){
cansuf[k-1][i]|=cansuf[k-1][i+1];
}
}
for(int i = 1; i < k; i++){
for(int j = c[i]+1; j < n; j++){
if(nextblank[j].ff <= j-c[i]){
canpref[i][j] = canpref[i-1][j-c[i]-1]&&s[j-c[i]]!='X';
}
if(s[j]!='X'){
canpref[i][j]|=canpref[i][j-1];
}
}
}
for(int i = k-2; i >= 0; i--){
for(int j = n-c[i]-2; j >= 0; j--){
if(nextblank[j].ss >= j+c[i]){
cansuf[i][j] = cansuf[i+1][j+c[i]+1]&&s[j+c[i]]!='X';
}
if(s[j]!='X'){
cansuf[i][j]|=cansuf[i][j+1];
}
}
}
vector<int> can0(n), can1(n);
for(int i = 0; i < n-2; i++){
can0[i] = cansuf[0][i+1]&&nextfull[i].ff == -INF;
}
for(int i = 1; i < n; i++){
can0[i] |= canpref[k-1][i-1] && nextfull[i].ss == INF;
}
for(int i = 1; i < n-1; i++){
for(int j = 0; j < k-1; j++){
can0[i]|=canpref[j][i-1]&&cansuf[j+1][i+1];
}
}
vector<int> delta(n+1);
if(k == 1){
for(int i = 0; i+c[0]-1 < n; i++){
int l = i, r = i+c[0]-1;
if(nextblank[i].ss > r && (i == 0 || nextfull[i-1].ff == -INF) && (r == n-1 || nextfull[r+1].ss == INF))
delta[l]++, delta[r+1]--;
}
} else{
for(int i = 0; i+c[0]+1 < n; i++){
int l = i, r = i+c[0]-1;
if(nextblank[i].ss > r && (i == 0 || nextfull[i-1].ff == -INF) && s[r+1] !='X' && cansuf[1][r+2])
delta[l]++, delta[r+1]--;
}
for(int i = 2; i+c[k-1]-1 < n; i++){
int l = i, r = i+c[k-1]-1;
if(nextblank[i].ss > r && (r == n-1 || nextfull[r+1].ss == INF) && s[i-1] !='X' && canpref[k-2][i-2])
delta[l]++, delta[r+1]--;
}
for(int i = 1; i < k-1; i++){
for(int j = 2; j+c[i]+1 < n; j++){
int l = j, r = j+c[i]-1;
if(nextblank[l].ss > r && s[l-1] != 'X' && s[r+1]!='X' && canpref[i-1][l-2] && cansuf[i+1][r+2])
delta[l]++, delta[r+1]--;
}
}
}
int cur = 0;
for(int i = 0; i < n; i++){
cur+=delta[i];
if(cur)
can1[i] = 1;
}
string resp(n,0);
for(int i = 0; i < n; i++){
if(can0[i]){
if(can1[i]){
resp[i] = '?';
} else {
resp[i] = '_';
}
} else {
resp[i]= 'X';
}
}
return resp;
}
