#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(a,x) for (auto &a : x)
#define D(x) //cerr << #x << ": " << x << endl;
vector<set<int>> fits;
vector<set<int>> rev_fits;
string s;
vi c;
int n, m;
void calc_fits() {
fits.assign(n, {});
bool had_x = false;
REP(i, n) {
if (s[i] == 'X') had_x = true;
if (!had_x) fits[i].insert(0);
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].count(d)) goto skip;}
else if (d != 0) goto skip;
fits[i].insert(d+1);
skip:;
}
if (s[i] != 'X' && i != 0) {
trav(el, fits[i-1]) {fits[i].insert(el);}
}
}
}
bool can_white(int i) {
set<int> left = {0}; set<int> right = {0};
if (i > 0) left = fits[i-1];
if (i < n-1) right = rev_fits[i+1];
trav(a, left) {
trav(b, right) {
if (a + b == m) return true;
}
}
return false;
}
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;
set<int> left = {0}; set<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.count(d)) goto fail;
if (!right.count(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;
}
