#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
constexpr int N = 2e3 + 5;
constexpr int K = 105;
int n, k;
void f(auto &dp, string s, vector<int> a) {
vector<int> p(n + 1);
for (int i = 1; i <= n; i++) {
p[i] = p[i - 1] + (s[i] == '_');
}
auto good = [&](int l, int r) {
if (p[r] - p[l - 1] > 0) return false;
return (s[l - 1] != 'X' && s[r + 1] != 'X');
};
dp[0][0][0] = dp[0][0][1] = 1;
for (int i = 1; i <= n; i++) {
if (s[i] != 'X') {
dp[i][0][0] = dp[i - 1][0][0];
dp[i][0][1] = dp[i - 1][0][1];
}
for (int j = 1; j <= k; j++) {
if (s[i] != 'X') {
dp[i][j][0] = (dp[i - 1][j][0] | dp[i - 1][j][1]);
}
if (s[i] != '_' && i >= a[j] && good(i - a[j] + 1, i) && dp[i - a[j]][j - 1][0]) {
dp[i][j][1] = 1;
}
}
}
}
string solve_puzzle(string s, vector<int> c) {
n = s.size();
k = c.size();
string t(n + 5, '!');
string s_rev(n + 5, '!');
for (int i = 1; i <= n; i++) {
t[i] = s[i - 1];
}
for (int i = n; i >= 1; i--) {
s_rev[i] = s[i - 1];
}
vector<int> a = {0}, c_rev = {0};
for (int i = 1; i <= k; i++) {
a.push_back(c[i - 1]);
}
for (int i = k; i >= 1; i--) {
c_rev.push_back(c[i - 1]);
}
vector<vector<vector<int>>> dp(N, vector<vector<int>>(K, vector<int>(2)));
vector<vector<vector<int>>> dp_rev(N, vector<vector<int>>(K, vector<int>(2)));
f(dp, t, a);
f(dp_rev, s_rev, c_rev);
string ans(n, '!');
for (int i = 1; i <= n; i++) {
if (s[i - 1] != '.') {
ans[i - 1] = s[i - 1];
continue;
}
bool w = false, bk = false;
for (int x = 0; x <= k; x++) {
if (dp[i][x][0] && dp_rev[n - i + 1][k - x][0]) {
w = true;
}
}
for (int b = 1; b <= k; b++) {
for (int j = i; j <= i + a[b] - 1; j++) {
if (j > n) break;
if (dp[j][b][1] && dp_rev[n - (j + 1) + 1][k - b][0]) {
bk = true;
}
}
}
if (w && !bk) ans[i - 1] = '_';
else if (!w && bk) ans[i - 1] = 'X';
else if (w && bk) ans[i - 1] = '?';
else abort();
}
return ans;
}
