#include <bits/stdc++.h>
//#include "grader.cpp"
#include "paint.h"
using namespace std;
const int N = 200005;
const int K = 105;
int n, k, w[N], b[N], dp[N][K][2];
string s;
vector <int> c;
int sum_b(int l, int r){
return b[r] - b[l - 1];
}
int sum_w(int l, int r){
return w[r] - w[l - 1];
}
int solve0(int i, int j){
if(i <= 0) return j == 0;
if(j == 0) return sum_b(1, i) == 0;
int &ret = dp[i][j][0];
if(ret != -1) return ret;
ret = 0;
if(s[i] == 'X' || s[i] == '.'){
if(i - c[j] + 1 >= 1 && sum_w(i - c[j] + 1, i) == 0 && s[i - c[j]] != 'X'){
ret |= solve0(i - c[j] - 1, j - 1);
}
}
if(s[i] == '_' || s[i] == '.'){
ret |= solve0(i - 1, j);
}
return ret;
}
int solve1(int i, int j){
if(i > n) return j == k + 1;
if(j == k + 1) return sum_b(i, n) == 0;
int &ret = dp[i][j][1];
if(ret != -1) return ret;
ret = 0;
if(s[i] == 'X' || s[i] == '.'){
if(i + c[j] - 1 <= n && sum_w(i, i + c[j] - 1) == 0 && s[i + c[j]] != 'X'){
ret |= solve1(i + c[j] + 1, j + 1);
}
}
if(s[i] == '_' || s[i] == '.'){
ret |= solve1(i + 1, j);
}
return ret;
}
bool check_w(int idx){
for(int j = 0 ; j <= k ; j++){
if(solve0(idx - 1, j) && solve1(idx + 1, j + 1)){
return 1;
}
}
return 0;
}
std::string solve_puzzle(std::string S, std::vector<int> C) {
s = S;
c = C;
n = s.size();
k = c.size();
c.insert(c.begin(), -1);
s = ';' + s;
s = s + ';';
for(int i = 1 ; i <= n ; i++)
w[i] = w[i - 1] + (s[i] == '_');
for(int i = 1 ; i <= n ; i++)
b[i] = b[i - 1] + (s[i] == 'X');
memset(dp, -1, sizeof dp);
vector <int> can_b(n + 5);
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= k ; j++){
if(i - c[j] + 1 >= 1 && sum_w(i - c[j] + 1, i) == 0 && s[i - c[j]] != 'X' && s[i + 1] != 'X' &&
solve0(i - c[j] - 1, j - 1) && solve1(i + 2, j + 1)){
can_b[i - c[j] + 1]++;
can_b[i + 1]--;
}
}
}
for(int i = 1 ; i <= n ; i++)
can_b[i] += can_b[i - 1];
string ret = "";
for(int i = 1 ; i <= n ; i++){
if(s[i] == 'X' || s[i] == '_'){
ret += s[i];
continue;
}
int cur = 0;
if(check_w(i)) cur |= 1;
if(can_b[i] > 0) cur |= 2;
if(cur == 1) ret += '_';
else if(cur == 2) ret += 'X';
else ret += '?';
}
return ret;
}
