#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
string solve_puzzle(string s, vector<int> blocks) {
int n = s.size();
int k = blocks.size();
// Make string 1-indexed
s = " " + s;
// Prefix sum: number of '_' up to i
vector<int> underscore(n + 1, 0);
for (int i = 1; i <= n; i++) {
underscore[i] = underscore[i - 1] + (s[i] == '_');
}
// Check if segment [l, r] has no '_'
auto can_fill = [&](int l, int r) {
return (underscore[r] - underscore[l - 1] == 0);
};
// dp1[i][j] = can we place first j blocks using prefix ending at i
vector<vector<bool>> dp1(n + 1, vector<bool>(k + 1, false));
for (int i = 0; i <= n; i++) dp1[i][0] = true;
for (int j = 1; j <= k; j++) {
int len = blocks[j - 1];
for (int i = 1; i <= n; i++) {
if (i < len) continue;
if (!can_fill(i - len + 1, i)) continue;
if (j == 1) {
dp1[i][j] = true;
} else {
if (i - len - 1 >= 0 && dp1[i - len - 1][j - 1]) {
dp1[i][j] = true;
}
}
}
}
// dp2[i][j] = can we place blocks j..k starting from i
vector<vector<bool>> dp2(n + 2, vector<bool>(k + 2, false));
for (int i = 1; i <= n + 1; i++) dp2[i][k + 1] = true;
for (int j = k; j >= 1; j--) {
int len = blocks[j - 1];
for (int i = n; i >= 1; i--) {
if (i + len - 1 > n) continue;
if (!can_fill(i, i + len - 1)) continue;
if (j == k) {
dp2[i][j] = true;
} else {
if (i + len + 1 <= n && dp2[i + len + 1][j + 1]) {
dp2[i][j] = true;
}
}
}
}
// Make dp prefix/suffix cumulative
for (int j = 0; j <= k; j++) {
for (int i = 1; i <= n; i++) {
dp1[i][j] = dp1[i][j] | dp1[i - 1][j];
}
}
for (int j = 1; j <= k + 1; j++) {
for (int i = n; i >= 1; i--) {
dp2[i][j] = dp2[i][j] | dp2[i + 1][j];
}
}
// Difference array to track possible coverage
vector<int> diff(n + 2, 0);
// Positions that are always black
vector<int> always_black(n + 1, 0);
for (int j = 1; j <= k; j++) {
int len = blocks[j - 1];
int left = 1, right = n;
for (int i = 1; i + len - 1 <= n; i++) {
bool ok = true;
// Check left side
if (j > 1) {
if (i - 2 < 0 || !dp1[i - 2][j - 1]) ok = false;
}
// Check right side
if (j < k) {
if (i + len + 1 > n || !dp2[i + len + 1][j + 1]) ok = false;
}
if (!ok) continue;
if (!can_fill(i, i + len - 1)) continue;
// Mark possible block placement
diff[i] += 1;
diff[i + len] -= 1;
left = max(left, i);
right = min(right, i + len - 1);
}
// Mark forced cells (intersection of all placements)
if (left <= right) {
for (int x = left; x <= right; x++) {
always_black[x] = 1;
}
}
}
// Build final answer
string ans = "";
int coverage = 0;
for (int i = 1; i <= n; i++) {
coverage += diff[i];
if (always_black[i]) ans += 'X';
else if (coverage == 0) ans += '_';
else ans += '?';
}
return ans;
}
