#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int MOD = (int)1e9 + 7;
const int NS = (int)2e5 + 4;
int N, k;
int dpl[NS][104], dpr[NS][104], jump[NS][104];
int jpref[104][NS];
int wpref[NS];
int lw[NS], rw[NS];
string ans;
std::string solve_puzzle(std::string s, std::vector<int> c) {
N = (int)s.size(), k = (int)c.size();
s = '?' + s;
c.push_back(0);
for(int i = 1; i <= N; ++i){
lw[i] = lw[i - 1];
if(s[i] == '_'){
lw[i] = i;
}
}
rw[N + 1] = N + 1;
for(int i = N; i >= 1; --i){
rw[i] = rw[i + 1];
if(s[i] == '_'){
rw[i] = i;
}
}
for(int i = k; i >= 1; --i){
c[i] = c[i - 1];
}
for(int i = 1; i <= N; ++i){
wpref[i] = wpref[i - 1] + (s[i] == '_');
}
dpl[0][0] = 1;
int canzero = 1;
for(int i = 1; i <= N; ++i){
if(s[i] == 'X'){
canzero = 0;
continue;
}
dpl[i][0] = canzero;
for(int j = 1; j <= k; ++j){
dpl[i][j] |= dpl[i - 1][j];
if(i - c[j] - 1 >= 0){
if(wpref[i - 1] - wpref[i - c[j] - 1]){
continue;
}
dpl[i][j] |= dpl[i - c[j] - 1][j - 1];
}
}
}
dpr[N + 1][k + 1] = 1; canzero = 1;
for(int i = N; i >= 1; --i){
if(s[i] == 'X'){
canzero = 0;
continue;
}
dpr[i][k + 1] = canzero;
for(int j = k; j >= 1; --j){
dpr[i][j] |= dpr[i + 1][j];
if(i + c[j] <= N){
if(wpref[i + c[j]] - wpref[i]){
continue;
}
dpr[i][j] |= dpr[i + c[j] + 1][j + 1];
}
}
}
for(int i = 0; i <= N; ++i){
if(s[i] == 'X'){
continue;
}
for(int j = 1; j <= k; ++j){
int r = i + c[j] + 1;
if(r > N + 1){
continue;
}
if(wpref[r - 1] - wpref[i]){
continue;
}
jump[i][j] = (dpl[i][j - 1] & dpr[r][j + 1]);
if(jump[i][j]){
++jpref[j][i];
}
}
}
for(int i = 1; i <= k; ++i){
for(int j = 1; j <= N + 1; ++j){
jpref[i][j] += jpref[i][j - 1];
}
}
for(int i = 1; i <= N; ++i){
if(s[i] != '.'){
ans += s[i];
continue;
}
int canw = 0, canb = 0;
for(int j = 0; j <= k; ++j){
if(dpl[i][j] & dpr[i][j + 1]){
canw = 1;
break;
}
}
if(!canw){
ans += 'X';
continue;
}
int l_ = lw[i], r_ = rw[i];
for(int j = 1; j <= k; ++j){
int posl = max(l_, i - c[j]), posr = min(r_, i + c[j]) - c[j] - 1;
if(posl > posr){
continue;
}
if(jpref[j][posr] - jpref[j][posl - 1]){
canb = 1;
break;
}
}
if(!canb){
ans += '_';
}
else{
ans += '?';
}
}
return ans;
}
