#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
string solve_puzzle(string s, vector<int> c) {
int n = s.size(), k = c.size();
s = " " + s;
ranges::reverse(c); c.push_back(0); ranges::reverse(c);
vector<int> p(n + 1);
for (int i = 1; i <= n; i++) {
p[i] = p[i - 1] + (s[i] == '_');
}
vector<vector<int>> dp(n + 1, vector<int>(k + 1));
for (int i = 0; i <= n; i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
if (j == 1 && i == c[j] && p[c[j]] == 0) {
dp[i][j] = 1;
continue;
}
bool ok = 0;
for (int t = 0; t < i - c[j]; t++) {
if (dp[t][j - 1]) {
ok = 1;
}
}
if (!ok) continue;
if (i - c[j] > 0 && s[i - c[j]] != 'X' && p[i] - p[i - c[j]] == 0) {
dp[i][j] = 1;
}
}
}
vector<vector<int>> dp_rev(n + 3, vector<int>(k + 2));
for (int i = 0; i <= n + 2; i++) {
dp_rev[i][k + 1] = 1;
}
for (int i = n; i >= 1; i--) {
for (int j = k; j >= 1; j--) {
if (j == k && i == n - c[k] + 1 && p[n] - p[n - c[k]] == 0) {
dp_rev[i][j] = 1;
continue;
}
bool ok = 0;
for (int t = i + c[j] + 1; t <= n + 2; t++) {
if (dp_rev[t][j + 1]) {
ok = 1;
}
}
if (!ok) continue;
if (i + c[j] <= n && s[i + c[j]] != 'X' && p[i + c[j]] - p[i] == 0) {
dp_rev[i][j] = 1;
}
}
}
vector<vector<array<int, 2>>> g(k + 1);
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
for (int t = i + 2; t <= n + 2; t++) {
if (dp[i][j] && dp_rev[t][j + 1]) {
g[j].push_back({i - c[j] + 1, i});
break;
}
}
}
}
string ans(n, '_');
for (int i = 1; i <= k; i++) {
int cnt = g[i].size();
vector<int> f(n + 3);
for (auto [l, r] : g[i]) {
f[r + 1]--;
f[l]++;
}
for (int i = 1; i <= n; i++) {
f[i] += f[i - 1];
}
for (int x = 1; x <= n; x++) {
if (f[x] == 0) continue;
if (f[x] == cnt) {
ans[x - 1] = 'X';
} else {
ans[x - 1] = '?';
}
}
}
return ans;
}
