#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
array<vector<vector<int>>, 2> get(string s, vector<int> c) {
int n = s.size();
int k = c.size();
s = " " + s;
ranges::reverse(c); c.push_back(0); ranges::reverse(c);
vector<vector<int>> w(n + 1, vector<int>(k + 1));
vector<vector<int>> b(n + 1, vector<int>(k + 1));
for (int i = 0; i <= n; i++) {
if (s[i] != 'X') {
w[i][0] = 1;
}
}
b[0][0] = 1;
vector<int> p(n + 1);
for (int i = 1; i <= n; i++) {
p[i] = p[i - 1] + (s[i] == '_');
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
if (b[i - 1][j] && s[i] != 'X') {
w[i][j] = 1;
}
if (w[i - 1][j] && s[i] != 'X') {
w[i][j] = 1;
}
if (i - c[j] >= 0 && p[i] - p[i - c[j]] == 0 && w[i - c[j]][j - 1]) {
b[i][j] = 1;
}
}
}
return {w, b};
}
string solve_puzzle(string s, vector<int> c) {
int n = s.size();
int k = c.size();
auto [w1, b1] = get(s, c);
ranges::reverse(s);
ranges::reverse(c);
auto [w2, b2] = get(s, c);
reverse(w2.begin() + 1, w2.end());
reverse(b2.begin() + 1, b2.end());
vector<bool> black(n + 1), white(n + 1);
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
if (w1[i][j] && w2[i][k - j]) {
white[i] = 1;
}
if (j == 0 && b2[i][k]) {
for (int x = i; x < i + c[0]; x++) {
black[x] = 1;
}
}
if (j == k && b1[i][k]) {
for (int x = i; x > i - c[j - 1]; x--) {
assert(x >= 0);
black[x] = 1;
}
}
if (j == 0 || j == k) continue;
for (int t = i + 2; t <= n; t++) {
if (b1[i][j] && b2[t][k - j]) {
for (int x = i; x > i - c[j - 1]; x--) {
assert(x >= 0);
black[x] = 1;
}
}
}
for (int t = i - 2; t >= 0; t--) {
if (b1[t][j] && b2[i][k - j]) {
for (int x = i; x < i + c[j - 1]; x++) {
assert(x <= n);
black[x] = 1;
}
}
}
}
}
string ans(n, ' ');
string str = " X_?";
for (int i = 1; i <= n; i++) {
int j = 0;
if (black[i]) j += 1;
if (white[i]) j += 2;
ans[i - 1] = str[j];
}
return ans;
}
