#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define REP(i,n) for (int i = 0; i < n; i++)
#define all(x) (x).begin(), (x).end()
#define trav(x) for (auto &a : x)
#define D(x) //cerr << #x << ": " << x << endl;
vi fits;
vi rev_fits;
string s;
vi c;
int n, m;
void calc_fits() {
fits = vi(n, 0);
REP(i, n) {
if (s[i] == '_') {fits[i] = fits[max(0,i-1)]; continue;}
REP(d, m) {
// try putting d
if (c[d] > i+1) continue;
for (int j = i+1-c[d]; j < i; j++) {
if (s[j] == '_') goto skip;
}
if (i-c[d] >= 0 && s[i-c[d]] == 'X') goto skip;
if (i-c[d]-1 >= 0) {if (fits[i-c[d]-1] != d) goto skip;}
else if (d != 0) goto skip;
fits[i] = d+1;
skip:;
}
if (s[i] != 'X') fits[i] = max(fits[i],fits[max(0,i-1)]);
}
}
bool can_white(int i) {
int left = 0; int right = 0;
if (i > 0) left = fits[i-1];
if (i < n-1) right = rev_fits[i+1];
return left + right >= m; // simplified!
}
bool can_black(int i) {
D(i);
REP(d, m) {
for (int fx = -c[d]+1; fx <= 0; fx++) {
D(fx);
int start = i+fx;
int end = start+c[d]-1;
int left = 0; int right = 0;
// fits?
if (start < 0) continue;
if (end > n-1) continue;
// is clear?
for (int j = start; j <= end; j++) {
if (s[j] == '_') goto fail;
}
//cerr << "clr\n";
// are bounds ok?
if (start > 0 && s[start-1] == 'X') goto fail;
if (end < n-1 && s[end+1] == 'X') goto fail;
// okay, what fits?
if (start > 1) left = fits[start-2];
if (end < n-2) right = rev_fits[end+2];
D(left); D(right);
// does it fit together?
if (left < d) goto fail;
if (right < m-1-d) goto fail;
// yay!
return true;
fail:;
}
}
return false;
}
std::string solve_puzzle(std::string s_, std::vector<int> c_) {
s = s_; c = c_; n = s.size(); m = c.size();
calc_fits();
swap(fits, rev_fits);
reverse(all(s)); reverse(all(c));
calc_fits();
swap(fits, rev_fits);
reverse(all(s)); reverse(all(c));
reverse(all(rev_fits));
REP(i, n) {
//cerr << fits[i] << " ";
}
//cerr << endl;
REP(i, n) {
//cerr << rev_fits[i] << " ";
}
//cerr << endl;
string ans(n, '?');
REP(i, n) {
if (s[i] != '.') ans[i] = s[i];
else {
if (!can_white(i)) ans[i] = 'X';
if (!can_black(i)) ans[i] = '_';
if (!can_white(i) && !can_black(i)) ans[i] = '!';
}
}
return ans;
}
