#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
char ss[200015];
int cc[200015];
int dp[200015][105];
int dp_rev[200015][105];
int ok_white[200015];
int ok_black[200015];
std::string solve_puzzle(std::string s, std::vector<int> c) {
int n = s.length(), k = c.size();
for(int i=2; i<=n+1; i++) ss[i] = s[i-2];
for(int i=1; i<=k; i++) cc[i] = c[i-1];
dp[0][0] = 1;
dp[1][0] = 1;
int black_able = 0;
for(int i=2; i<=n+1; i++){
if(ss[i] != '_') black_able++;
else black_able = 0;
if(ss[i] != 'X') for(int j=0; j<=k; j++) dp[i][j] = dp[i-1][j];
for(int j=1; j<=k; j++){
if(cc[j] > black_able) continue;
if(ss[i-cc[j]] == 'X') continue;
dp[i][j] |= dp[i-cc[j]-1][j-1];
}
}
/*
for(int i=2; i<=n+1; i++){
for(int j=0; j<=k; j++) printf("%d ", dp[i][j]);
printf("\n");
}
*/
dp_rev[n+3][k+1] = 1;
dp_rev[n+2][k+1] = 1;
black_able = 0;
for(int i=n+1; i>=2; i--){
if(ss[i] != '_') black_able++;
else black_able = 0;
if(ss[i] != 'X') for(int j=1; j<=k+1; j++) dp_rev[i][j] = dp_rev[i+1][j];
for(int j=1; j<=k; j++){
if(cc[j] > black_able) continue;
if(ss[i+cc[j]] == 'X') continue;
dp_rev[i][j] |= dp_rev[i+cc[j]+1][j+1];
}
}
/*
printf("=\n");
for(int i=2; i<=n+1; i++){
for(int j=1; j<=k+1; j++) printf("%d ", dp_rev[i][j]);
printf("\n");
}
*/
// Check white-ability
for(int i=2; i<=n+1; i++){
for(int j=0; j<=k; j++) ok_white[i] |= (dp[i-1][j] & dp_rev[i+1][j+1]);
}
// Check black-ability
for(int j=1; j<=k; j++){
int must_white = 0;
for(int i=2; i<=2+cc[j]-1; i++){
if(ss[i] == '_') must_white++;
}
int last_valid = 0;
for(int i=2; i<=n+1-cc[j]+1; i++){
if(must_white == 0 && ss[i-1] != 'X' && ss[i+cc[j]] != 'X' && dp[i-2][j-1] && dp_rev[i+cc[j]+1][j+1]){
last_valid = i+cc[j]-1;
}
if(i <= last_valid) ok_black[i] = 1;
must_white -= (ss[i] == '_');
must_white += (ss[i+cc[j]] == '_');
}
for(int i=n+1-cc[j]+2; i<=n+1; i++) if(i <= last_valid) ok_black[i] = 1;
}
string res;
for(int i=2; i<=n+1; i++){
if(ss[i] != '.') res += ss[i];
else if(ok_black[i] && ok_white[i]) res += '?';
else if(ok_black[i]) res += 'X';
else if(ok_white[i]) res += '_';
else exit(1);
}
return res;
}
