#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5, maxk = 105, INF = 1e9;
int n, k;
bool dp[maxn][maxk][2];
int dpsum[maxn][maxk][2];
bool ansb[maxn], answ[maxn];
bool qry(int il, int ir, int j, int ii) {
if (il > ir) return 0;
if (ii == 0) {
int val = dpsum[ir][j][ii];
if (il-1 >= 0) val -= dpsum[il-1][j][ii];
return val;
} else if (ii == 1) {
int val = dpsum[il][j][ii];
if (ir+1 < n) val -= dpsum[ir+1][j][ii];
return val;
}
return 69420;
}
string solve_puzzle(string s, vector<int> c) {
k = c.size();
c.push_back(1);
for (int i=k;i>=1;i--) swap(c[i-1], c[i]);
c.push_back(1);
s = "X_" + s + "_X";
n = s.size();
int lastw[n], lastb[n];
lastw[0] = -INF, lastb[0] = 0;
for (int i=1;i<n;i++) {
lastw[i] = lastw[i-1], lastb[i] = lastb[i-1];
if (s[i] == 'X') lastb[i] = i;
if (s[i] == '_') lastw[i] = i;
}
dp[0][0][0] = dpsum[0][0][0] = 1;
for (int i=1;i<=k+1;i++) dp[0][i][0] = dpsum[0][i][0] = 0;
for (int i=0;i<=k+1;i++) dp[1][i][0] = 0, dpsum[1][i][0] = dp[0][i][0];
for (int i=2;i<n;i++) {
int w = lastw[i];
dpsum[i][0][0] = dpsum[i-1][0][0];
for (int j=1;j<=k+1;j++) {
int pos = i - c[j];
dp[i][j][0] = (i - lastw[i] >= c[j] && qry(lastb[pos], pos - 1, j-1, 0));
dpsum[i][j][0] = dpsum[i-1][j][0] + dp[i][j][0];
}
}
int nextb[n], nextw[n];
nextw[n-1] = INF, nextb[n-1] = n-1;
for (int i=n-2;i>=0;i--) {
nextw[i] = nextw[i+1], nextb[i] = nextb[i+1];
if (s[i] == 'X') nextb[i] = i;
if (s[i] == '_') nextw[i] = i;
}
dp[n-1][k+1][1] = dpsum[n-1][k+1][1] = 1;
for (int i=0;i<=k;i++) dp[n-1][i][1] = dpsum[n-1][i][1] = 0;
for (int i=0;i<=k+1;i++) dp[n-2][i][1] = 0, dpsum[n-2][i][1] = dpsum[n-1][i][1];
for (int i=n-3;i>=0;i--) {
int w = nextw[i];
dpsum[i][k+1][1] = dpsum[i+1][k+1][1];
for (int j=0;j<=k;j++) {
int pos = i + c[j];
dp[i][j][1] = (nextw[i] - i >= c[j] && qry(pos + 1, nextb[pos], j+1, 1));
dpsum[i][j][1] = dpsum[i+1][j][1] + dp[i][j][1];
}
}
// for (int j=0;j<=k+1;j++) {
// for (int i=0;i<n;i++) cout << dp[i][j][0] << " "; cout << endl;
// }
// cout << endl;
// for (int j=0;j<=k+1;j++) {
// for (int i=0;i<n;i++) cout << dp[i][j][1] << " "; cout << endl;
// }
// cout << endl;
for (int i=0;i<n;i++) for (int j=0;j<=k+1;j++) {
if (i - c[j] + 1 >= 0) dp[i][j][0] &= dp[i - c[j] + 1][j][1];
dpsum[i][j][0] = dp[i][j][0];
if (i > 0) dpsum[i][j][0] += dpsum[i-1][j][0];
}
for (int i=n-1;i>=0;i--) for (int j=0;j<=k+1;j++) {
if (i + c[j] - 1 < n) dp[i][j][1] &= dp[i + c[j] - 1][j][0];
dpsum[i][j][1] = dp[i][j][1];
if (i < n-1) dpsum[i][j][1] += dpsum[i+1][j][1];
}
// for (int j=0;j<=k+1;j++) {
// for (int i=0;i<n;i++) cout << dp[i][j][0] << " "; cout << endl;
// }
// cout << endl;
// for (int j=0;j<=k+1;j++) {
// for (int i=0;i<n;i++) cout << dp[i][j][1] << " "; cout << endl;
// }
// cout << endl;
for (int i=2;i<n-2;i++) {
answ[i] = ansb[i] = 0;
for (int j=0;j<=k;j++) answ[i] |= (qry(lastb[i], i-1, j, 0) && qry(i+1, nextb[i], j+1, 1));
for (int j=1;j<=k;j++) ansb[i] |= qry(i, min(i + c[j] - 1, n-1), j, 0);
}
// for (int i=2;i<n-2;i++) cout << answ[i] << " "; cout << endl;
// for (int i=2;i<n-2;i++) cout << ansb[i] << " "; cout << endl;
string ans;
for (int i=2;i<n-2;i++) {
if (answ[i] && ansb[i]) ans += '?';
else if (answ[i]) ans += '_';
else if (ansb[i]) ans += 'X';
}
return ans;
}
