#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int whites[200005];
bool white[200005];
int black[200005];
bool dp1[200005][105];
bool dp2[200005][105];
int count_white(int l, int r){
l = max(1, l);
int x = whites[r] - whites[l-1];
return x == 0;
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
int k = c.size();
int n = s.size();
for(int i=1; i<=n; i++){
if(s[i-1] == '_') whites[i] = 1;
whites[i] += whites[i-1];
}
dp1[0][0] = 1;
for(int i=1; i<=n+2; i++){
dp1[i][0] |= dp1[i-1][0];
if(i <= n && s[i-1] == 'X') dp1[i][0] = 0;
}
dp2[n+2][k+1] = 1;
for(int i=n+1; i>=0; i--){
dp2[i][k+1] |= dp2[i+1][k+1];
if(1 <= i && i <= n && s[i-1] == 'X') dp2[i][k+1] = 0;
}
for(int j=1; j<=k; j++){
for(int i=1; i<=n; i++){
if(s[i-1] == '_'){
dp1[i][j] |= dp1[i-1][j];
}
else if(s[i-1] == 'X'){
if(i >= c[j-1] && (i == n || s[i] != 'X') && (i == c[j-1] || s[i-c[j-1]-1] != 'X') && count_white(i-c[j-1]+1, i)){
dp1[i][j] |= dp1[max(0, i-c[j-1]-1)][j-1];
}
}
else{
dp1[i][j] |= dp1[i-1][j];
if(i >= c[j-1] && (i == n || s[i] != 'X') && (i == c[j-1] || s[i-c[j-1]-1] != 'X') && count_white(i-c[j-1]+1, i)){
dp1[i][j] |= dp1[max(0, i-c[j-1]-1)][j-1];
}
}
}
}
for(int j=k; j>=1; j--){
for(int i=n; i>=1; i--){
if(s[i-1] == '_'){
dp2[i][j] |= dp2[i+1][j];
}
else if(s[i-1] == 'X'){
if(i+c[j-1]-1 <= n && (i == 1 || s[i-2] != 'X') && (i+c[j-1] == n+1 || s[i+c[j-1]-1] != 'X') && count_white(i, i+c[j-1]-1)){
dp2[i][j] |= dp2[i+c[j-1]+1][j+1];
}
}
else{
dp2[i][j] |= dp2[i+1][j];
if(i+c[j-1]-1 <= n && (i == 1 || s[i-2] != 'X') && (i+c[j-1] == n+1 || s[i+c[j-1]-1] != 'X') && count_white(i, i+c[j-1]-1)){
dp2[i][j] |= dp2[i+c[j-1]+1][j+1];
}
}
}
}
for(int i=1; i<=n; i++){
if(s[i-1] == 'X') continue;
for(int j=0; j<=k; j++){
if(dp1[i-1][j] && dp2[i+1][j+1]) white[i] = 1;
}
}
for(int j=1; j<=k; j++){
for(int i=c[j-1]; i<=n; i++){
if(count_white(i-c[j-1]+1, i) && (i == c[j-1] || s[i-c[j-1]-1] != 'X') && (i == n || s[i] != 'X') && dp1[max(0, i-c[j-1]-1)][j-1] && dp2[min(n+1, i+2)][j+1]){
black[i-c[j-1]+1]++;
black[i+1]--;
}
}
}
string sol = "";
int tren = 0;
for(int i=1; i<=n; i++){
tren += black[i];
if(tren && white[i]){
sol += '?';
}
else if(tren){
sol += 'X';
}
else sol += '_';
}
return sol;
}
