#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using ll = long long;
using ld = long double;
using pr = pair<int, int>;
const int MOD = 1e9+7, MAXA = 1e6;
vector<vector<bool>> used;
vector<vector<bool>> dpp(const string& s, const vector<int>& c, bool finder) {
int n = s.size(), k = c.size();
vector<vector<bool>> dp(n+2, vector<bool> (k+1, 0));
vector<int> pref(n+2);
for (int i = 0; i < n; i++)
pref[i+1] = pref[i] + (s[i] == '_');
dp[0][0] = 1;
for (int i = 1; i <= n+1; i++) {
char cur;
if (i <= n) cur = s[i-1];
else cur = '_';
if (cur == '.' || cur == '_') dp[i][0] = dp[i-1][0];
for (int j = 1; j <= k; j++) {
if (cur == '.' || cur == '_') {
dp[i][j] = dp[i][j] || dp[i-1][j];
}
if (cur == '.' || cur == '_') {
int coor = i - c[j-1] - 1;
if (coor < 0) continue;
else {
if (pref[i-1] - pref[coor] == 0 && dp[coor][j-1]) {
dp[i][j] = 1;
if (finder == 1) used[i-1][j] = 1;
}
}
}
}
}
return dp;
}
string solve_puzzle(string s, vector<int> c) {
int n = s.size(), k = c.size();
used.resize(n+2, vector<bool> (k+1, 0));
vector<vector<bool>> dp1, dp2;
dp1 = dpp(s, c, 1);
reverse(s.begin(), s.end());
reverse(c.begin(), c.end());
dp2 = dpp(s, c, 0);
reverse(s.begin(), s.end());
reverse(c.begin(), c.end());
// reverse(dp2.begin(), dp2.end());
string res;
vector<int> pref(n+2);
for (int i = 0; i < n; i++)
pref[i+1] = pref[i] + (s[i] == '_');
vector<bool> white(n+2, 0), black(n+2, 0);
for (int i = 1; i <= n+1; i++) {
for (int j = 0; j <= k; j++) {
if (dp1[i][j] && dp2[n-i+1][k-j]) {
white[i] = 1;
for (int l = 1; l < i; l++) {
if (black[l]) continue;
if (j > 0) {
int start = i - c[j-1];
int end = i - 1;
if (start >= 0) {
if (pref[i-1] - pref[start] == 0 && dp1[start][j-1]) {
for (int pos = start; pos <= end; pos++) {
black[pos+1] = 1;
}
}
}
}
}
}
}
}
// for (int j = 0; j <= k; j++) {
// for (int i = 1; i <= n+1; i++) {
// cout << dp1[i][j] << ' ';
// }
// cout << '\n';
// }
// for (int j = 0; j <= k; j++) {
// for (int i = 1; i <= n+1; i++) {
// cout << dp2[i][j] << ' ';
// }
// cout << '\n';
// }
// for (int j = 0; j <= k; j++) {
// for (int i = 1; i <= n+1; i++) {
// cout << used[i][j] << ' ';
// }
// cout << '\n';
// }
for (int i = 1; i <= n; i++) {
if (white[i] && black[i]) {
res += '?';
}
else if (white[i]) {
res += '_';
}
else if (black[i]) {
res += 'X';
}
else return "";
}
return res;
}
