#include "paint.h"
#include <bits/stdc++.h>
#include <cstdlib>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define sep ' '
#define debug(x) cerr << #x << ": " << x << endl;
const int MAXN = 2e5 + 10;
const int MAXK = 200 + 5;
int n, k, B[MAXN];
bool dp[MAXN][MAXK][2], dp2[MAXN][MAXK][2], W[MAXN];
inline void calc(string s, vector<int> c) {
s.insert(s.begin(), '#');
c.insert(c.begin(), 0);
int max_black = 0;
dp[0][0][0] = true;
for (int i = 1; i <= n; i++) {
bool poss_black = (s[i] != '_');
bool poss_white = (s[i] != 'X');
max_black = (poss_black ? max_black + 1 : 0);
for (int j = 0; j <= n; j++) {
dp[i][j][0] = ((dp[i - 1][j][0] || dp[i - 1][j][1]) && poss_white);
if (j && i >= c[j] && max_black >= c[j]) dp[i][j][1] = dp[i - c[j]][j - 1][0];
}
}
}
string solve_puzzle(string s, vector<int> c) {
n = s.size();
k = c.size();
calc(s, c);
reverse(all(s));
swap(dp, dp2);
reverse(all(c));
calc(s, c);
reverse(all(s));
swap(dp, dp2);
reverse(all(c));
c.insert(c.begin(), 0);
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
W[i] |= (dp[i][j][0] && dp2[n - i + 1][k - j][0]);
if (j && dp[i][j][1] && dp2[n - i][k - j][0])
B[i - c[j] + 1]++, B[i + 1]--;
}
}
for (int i = 1; i <= n; i++)
B[i] += B[i - 1];
string ans = "";
for (int i = 1; i <= n; i++) {
if (B[i] && W[i]) ans.push_back('?');
else if (B[i]) ans.push_back('X');
else if (W[i]) ans.push_back('_');
else ans.push_back('?'); // assert
}
return ans;
}
