#include <bits/stdc++.h>
#include "paint.h"
template <class T>
using Vec = std::vector<T>;
using String = std::string;
Vec<Vec<char>> precompute(const String &s, const Vec<int> &c) {
const int n = (int) s.size();
const int k = (int) c.size();
Vec<int> count(n + 1);
for (int i = 0; i < n; ++i) {
count[i + 1] = count[i] + (s[i] == '_');
}
Vec<Vec<char>> dp(n + 1, Vec<char>(k + 1));
dp[0][0] = true;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= k; ++j) {
if (!dp[i][j]) {
continue;
}
if (s[i] != 'X') {
dp[i + 1][j] = true;
if (j != k) {
const int l = i + 1;
const int r = l + c[j];
if (r <= n && count[r] - count[l] == 0) {
dp[r][j + 1] = true;
}
}
}
if (j == 0) {
const int l = i;
const int r = l + c[j];
if (r <= n && count[r] - count[l] == 0) {
dp[r][j + 1] = true;
}
}
}
}
return dp;
}
String solve_puzzle(String s, Vec<int> c) {
const int n = (int) s.size();
const int k = (int) c.size();
const auto left = precompute(s, c);
const auto right = precompute(String(s.rbegin(), s.rend()), Vec<int>(c.rbegin(), c.rend()));
Vec<char> white(n);
for (int i = 0; i < n; ++i) {
if (s[i] != 'X') {
for (int j = 0; j <= k; ++j) {
if (left[i][j] && right[n - i - 1][k - j]) {
white[i] = true;
break;
}
}
}
}
Vec<int> count(n + 1);
for (int i = 0; i < n; ++i) {
count[i + 1] = count[i] + (s[i] == '_');
}
Vec<int> black(n + 1);
for (int j = 0; j < k; ++j) {
for (int l = 0; l < n; ++l) {
const int r = l + c[j];
if (r > n) {
break;
}
const bool left_ok = [&] {
if (l == 0) return j == 0;
return s[l - 1] != 'X' && left[l - 1][j];
}();
const bool right_ok = [&] {
if (r == n) return j + 1 == k;
return s[r] != 'X' && right[n - r - 1][k - j - 1];
}();
if (left_ok && right_ok && count[r] - count[l] == 0) {
black[l] += 1;
black[r] -= 1;
}
}
}
for (int i = 0; i < n; ++i) {
black[i + 1] += black[i];
}
String ret(n, '?');
for (int i = 0; i < n; ++i) {
if (!white[i]) {
ret[i] = 'X';
}
if (!black[i]) {
ret[i] = '_';
}
}
return ret;
}
