#include "bits/stdc++.h"
#include "paint.h"
using namespace std;
#define MAX_N 200005
#define MAX_K 102
int N ,K;
string board;
vector <int> wh ,bl ,block;
bool check(int l ,int r){
if(r >= N)
return false;
if(wh[r+1] != wh[l])
return false;
if(r+1 < N && board[r+1] == 'X')
return false;
return true;
}
bool can_white[MAX_N];
int can_black[MAX_N];
bool vis[MAX_K][MAX_N];
bool can[MAX_K][MAX_N];
bool go(int i ,int j){
if(i >= N)
return j == K;
bool&good = can[j][i];
if(vis[j][i])
return good;
vis[j][i] = true;
if(board[i] != 'X' && go(i+1 ,j)){
good = true;
can_white[i] = true;
}
if(j != K && check(i ,i+block[j]-1) && go(i+block[j]+1 ,j+1)){
good = true;
can_black[i]++;
can_black[i+block[j]]--;
if(i+block[j] < N)
can_white[i+block[j]] = true;
}
return good;
}
string solve_puzzle(string s, vector<int> c){
N = s.size();
K = c.size();
board = s;
block = c;
wh.resize(N+1);
bl.resize(N+1);
for(int i = 0; i < N; i++){
bl[i+1] = bl[i] + (s[i] == 'X');
wh[i+1] = wh[i] + (s[i] == '_');
}
assert(go(0 ,0));
for(int i = 0; i <= N; i++)
can_black[i] += (i? can_black[i-1] : 0);
string ans;
for(int i = 0; i < N; i++){
if(can_white[i] && can_black[i])
ans += '?';
else if(can_black[i])
ans += 'X';
else if(can_white[i])
ans += '_';
else
assert(false);
}
return ans;
}
