#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+1) val -= dpsum[ir+1][j][ii];
return val;
}
return 69420;
}
string solve_puzzle(string s, vector<int> c) {
n = s.size(), k = c.size();
c.push_back(0);
for (int i=k;i>=1;i--) swap(c[i-1], c[i]);
s = '_' + s;
int lastw[n+1], lastb[n+1];
lastw[0] = 0, 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;i++) dp[0][i][0] = dpsum[0][i][0] = 0;
for (int i=1;i<=n;i++) {
int w = lastw[i];
dp[i][0][0] = (lastb[i] == 0);
dpsum[i][0][0] = dpsum[i-1][0][0] + dp[i][0][0];
for (int j=1;j<=k;j++) {
int pos = i - c[j];
dp[i][j][0] = (i - lastw[i] >= c[j] && (pos == 0 && j-1 == 0 || (qry(lastb[pos], pos - 1, j-1, 0))));
dpsum[i][j][0] = dp[i-1][j][0] + dp[i][j][0];
}
}
int nextb[n+2], nextw[n+2];
nextb[n+1] = nextw[n+1] = n+1;
for (int i=n;i>=1;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=1;i<=k;i++) dp[n+1][i][1] = dpsum[n+1][i][1] = 0;
for (int i=n;i>=1;i--) {
int w = nextw[i];
dp[i][k+1][1] = (nextb[i] == n+1);
dpsum[i][k+1][1] = dpsum[i+1][k+1][1] + dp[i][k+1][1];
for (int j=1;j<=k;j++) {
int pos = i + c[j];
dp[i][j][1] = (nextw[i] - i >= c[j] && (pos == n+1 && j+1 == k+1 || qry(pos + 1, nextb[pos], j+1, 1)));
dpsum[i][j][1] = dp[i+1][j][1] + dp[i][j][1];
}
}
for (int i=1;i<=n;i++) for (int j=1;j<=k;j++) {
if (i - c[j] + 1 >= 1) dp[i][j][0] &= dp[i - c[j] + 1][j][1];
dpsum[i][j][0] = dpsum[i-1][j][0] + dp[i][j][0];
}
for (int i=n;i>=1;i--) for (int j=1;j<=k;j++) {
if (i + c[j] - 1 <= n) dp[i][j][1] &= dp[i + c[j] - 1][j][0];
dpsum[i][j][1] = dpsum[i+1][j][1] + dp[i][j][1];
}
for (int i=1;i<=n;i++) {
answ[i] = ansb[i] = 0;
for (int j=0;j<=k;j++) answ[i] |= (dpsum[i-1][j][0] && dpsum[i+1][j+1][1]);
for (int j=1;j<=k;j++) ansb[i] |= qry(i, min(i + c[j] - 1, n), j, 0);
}
string ans;
for (int i=1;i<=n;i++) {
if (answ[i] && ansb[i]) ans += '?';
else if (answ[i]) ans += '_';
else if (ansb[i]) ans += 'X';
}
return ans;
}
