#include "paint.h"
#undef LOCAL
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/ioi/contests/ioi16d2/debug.h"
#else
#define debug(...) void(37)
#endif
bool good(string S, vector<int> c) {
int N = int(S.size());
int K = int(c.size());
vector<int> pref(N + 1);
for (int i = 0; i < N; ++i) {
pref[i + 1] = pref[i] + (S[i] == '_');
}
vector<vector<bool>> norm(N + 2, vector<bool>(K + 1, false));
{
norm[0][0] = true;
for (int i = 0; i < N; ++i) {
for (int j = 0; j <= K; ++j) {
if (!norm[i][j]) continue;
if (S[i] != 'X') norm[i + 1][j] = true;
int s = (j == K ? N + 1 : c[j]);
if (j < K && i + s <= N && pref[i + s] - pref[i] == 0) {
int to = i + s + 1;
norm[to][j + 1] = true;
}
}
}
}
debug(S, c, norm);
return norm[N][K] || norm[N + 1][K];
}
std::string solve_puzzle(std::string S, std::vector<int> c) {
debug(S);
int N = int(S.size());
int K = int(c.size());
vector<int> pref(N + 1);
for (int i = 0; i < N; ++i) {
pref[i + 1] = pref[i] + (S[i] == '_');
}
vector<vector<bool>> norm(N + 2, vector<bool>(K + 1, false));
auto rev = norm;
{
norm[0][0] = true;
for (int i = 0; i < N; ++i) {
for (int j = 0; j <= K; ++j) {
if (!norm[i][j]) continue;
if (S[i] != 'X') norm[i + 1][j] = true;
int s = (j == K ? N + 1 : c[j]);
if (j < K && i + s <= N && pref[i + s] - pref[i] == 0 && (i + s == N || S[i + s] != 'X')) {
int to = i + s + 1;
norm[to][j + 1] = true;
}
}
}
}
debug(norm);
{
rev[N][K] = true;
for (int i = N - 1; i >= 0; --i) {
for (int j = 0; j <= K; ++j) {
if (!rev[i + 1][j]) continue;
if (S[i] != 'X') rev[i][j] = true;
int s = (j == 0 ? N + 1 : c[j - 1]);
if (j > 0 && i >= s && pref[i + 1] - pref[i + 1 - s] == 0 && S[i - s] != 'X') {
rev[i - s][j - 1] = true;
}
}
}
}
debug(rev);
vector<int> sums(N + 1);
for (int j = 0; j < K; ++j) {
int s = c[j];
for (int i = 0; i + s <= N; ++i) {
if (norm[i][j] && rev[i + s][j + 1] && pref[i + s] - pref[i] == 0) {
sums[i + s] -= 1;
sums[i] += 1;
#ifdef LOCAL
auto _s = S;
for (int q = i; q < i + s; ++q) _s[q] = '1';
assert(good(_s, c));
#endif
}
}
}
for (int i = 0; i < N; ++i) {
sums[i + 1] += sums[i];
}
string res(N, '*');
for (int i = 0; i < N; ++i) {
bool black = sums[i] > 0;
bool white = false;
for (int j = 0; j <= K; ++j) {
if (S[i] != 'X' && norm[i + 1][j] && rev[i][j]) {
white = true;
}
}
debug(i, black, white);
#ifdef LOCAL
{
auto s = S;
s[i] = 'X';
assert(good(s, c) == black);
}
{
auto s = S;
s[i] = '_';
assert(good(s, c) == white);
}
#endif
if (black && white) {
res[i] = '?';
} else if (black) {
res[i] = 'X';
} else if (white) {
res[i] = '_';
} else {
assert(false);
}
}
return res;
}
