#include "paint.h"
#include <bits/stdc++.h>
#include <cstdlib>
using namespace std;
const int S_MAX_LEN = 200 * 1000 + 5;
int qs_[S_MAX_LEN], qsX[S_MAX_LEN], most_left[S_MAX_LEN], most_right[S_MAX_LEN], dpL[S_MAX_LEN][102], dpR[S_MAX_LEN][102];
std::string solve_puzzle(std::string s, std::vector<int> c) {
int sz = s.size(), k = c.size(), now = 0;
string res = "";
s = "_" + s + "_";
for(int i=1; i<=sz+1; i++) {
qs_[i] += qs_[i-1] + (s[i] == '_');
qsX[i] += qsX[i-1] + (s[i] == 'X');
}
for(int i=1; i<=sz; i++) {
if(s[i] == 'X' && now == 0) now = i;
else if(s[i] != 'X') now = 0;
most_left[i] = now;
}
now = 0;
for(int i=sz; i>=1; i--) {
if(s[i] == 'X' && now == 0) now = i;
else if(s[i] != 'X') now = 0;
most_right[i] = now;
}
for(int j=0; j<k; j++) {
int x = c[j];
for(int i=x; i<=sz; i++) {
if(s[i] == 'X') {
if(qs_[i] - qs_[i-x] == 0) dpL[i][j] = (j-1 < 0 ? 1 : dpL[i-x-1][j-1]);
else dpL[i][j] = 0;
}
else if(qs_[i] - qs_[i-x] == 0 && s[i-x] != 'X') {
if(j == 0) dpL[i][j] = 1;
else dpL[i][j] = max(dpL[i-1][j], dpL[i-x-1][j-1]);
}
else dpL[i][j] = dpL[i-1][j];
}
}
for(int j=k-1; j>-1; j--) {
int x = c[j];
for(int i=sz-x+1; i>=1; i--) {
if(s[i] == 'X') {
if(qs_[i+x-1] - qs_[i-1] == 0) dpR[i][j] = (j+1 == k ? 1 : dpR[i+x+1][j+1]);
else dpR[i][j] = 0;
}
else if(qs_[i+x-1] - qs_[i-1] == 0 && s[i+x] != 'X') {
if(j == k-1) dpR[i][j] = 1;
else dpR[i][j] = max(dpR[i+1][j], dpR[i+x+1][j+1]);
}
else dpR[i][j] = dpR[i+1][j];
}
}
for(int i=1; i<=sz; i++) {
if(s[i] != '.') {
res += s[i];
continue;
}
bool canX = 0, can_ = 0;
// _
if((qsX[i] == 0 && dpR[i+1][0]) || (qsX[sz] - qsX[i-1] == 0 && dpL[i-1][k-1])) can_ = true;
for(int j=0; j<k-1; j++) if(dpL[i-1][j] + dpR[i+1][j+1] == 2) can_ = true;
// X
int l = (most_left[i-1] == 0 ? i : most_left[i-1]);
int r = (most_right[i+1] == 0 ? i : most_right[i+1]);
for(int j=0; j<k; j++) {
if(c[j] >= r - l + 1) {
for(int a=r; a<=min(sz, l+c[j]-1); a++) {
if(qs_[a] - qs_[a-c[j]] > 0) continue;
if(s[a-c[j]] !='X' && s[a+1]!='X') {
if((j-1<0 ? (qsX[a-c[j]]>0 ? 0 : 1) : (a-c[j]-1<1 ? 0 : dpL[a-c[j]-1][j-1])) && (j+1>=k ? (qsX[sz]-qsX[a]>0 ? 0 : 1) : (a+2>sz ? 0 : dpR[a+2][j+1]))) canX = true;
}
}
}
}
if(can_ && canX) res += '?';
else if(can_) res += '_';
else res += 'X';
}
return res;
}
