#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
const int INF=0x3f3f3f3f;
const int N=2e5+2;
const int K=102;
int n, k;
int dp[N][K];
int pref[2][N];
int crn[N], bel[N];
string res;
#define DEBUG 0
string solve_puzzle(string s, vector<int> c) {
n=s.size(); k=c.size();
s=" "+s;
pref[0][0]=pref[1][0]=0;
for (int i=1; i<=n; ++i) {
pref[0][i]=pref[0][i-1]+(s[i]=='_');
pref[1][i]=pref[1][i-1]+(s[i]=='X');
}
memset(dp, 0, sizeof dp);
memset(crn, 0, sizeof crn);
memset(bel, 0, sizeof bel);
dp[0][0]=1;
for (int i=1; i<=n; ++i) {
if (s[i]!='X') dp[i][0]=dp[i-1][0];
for (int j=1; j<=k; ++j) {
if (s[i]!='X') dp[i][j]|=dp[i-1][j];
int dod=1;
if (j==1 && i==c[j-1]) dod=0;
if (i>=c[j-1] && pref[0][i]-pref[0][i-c[j-1]]==0 && s[i-c[j-1]]!='X') dp[i][j]|=dp[i-c[j-1]-dod][j-1];
}
}
#if DEBUG
for (int i=k; i>=0; --i) {
for (int j=0; j<=n; ++j) {
printf("%d ", dp[j][i]);
}
printf("\n");
}
printf("----------------\n");
#endif // DEBUG
assert(dp[n][k]);
dp[n][k]++;
for (int i=n; i>0; --i) {
for (int j=0; j<=k; ++j) {
if (dp[i][j]<2) continue;
if (s[i]!='X' && dp[i-1][j]) {
dp[i-1][j]++;
bel[i]++;
}
int dod=1;
if (j==1 && i==c[j-1]) dod=0;
if (j && i>=c[j-1] && pref[0][i]-pref[0][i-c[j-1]]==0 && s[i-c[j-1]]!='X' && dp[i-c[j-1]-dod][j-1]) {
crn[i-c[j-1]+1]++; crn[i+1]--; bel[i-c[j-1]]++;
// printf("interval: [%d, %d]\n", i-c[j-1]+1, i);
dp[i-c[j-1]-dod][j-1]++;
}
}
}
#if DEBUG
for (int i=k; i>=0; --i) {
for (int j=0; j<=n; ++j) {
printf("%d ", dp[j][i]>1 ? 1 : 0);
}
printf("\n");
}
printf("----------------\n");
#endif // DEBUG
crn[0]=0;
for (int i=1; i<=n; ++i) crn[i]+=crn[i-1];
for (int i=1; i<=n; ++i) {
if (bel[i] && crn[i]) res+='?';
else if (crn[i]) res+='X';
else if (bel[i]) res+='_';
else assert(0);
}
return res;
}
