#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+3;
const int K=104;
int n, k;
vector <int> c;
int dp[N][K][2];
int pref[2][N];
int crn[N], bel[N];
string res;
#define DEBUG 0
int rek(int i, int j, int fl) {
if (i==n+1) return j==k;
int &ret=dp[i][j][fl];
if (ret!=-1) return ret;
int curr;
ret=0;
if (pref[1][i]==pref[1][i-1]) {
curr=rek(i+1, j, 0);
if (curr) bel[i]++, ret=1;
}
if (!fl && j<k && i+c[j]<=n+1 && pref[0][i+c[j]-1]-pref[0][i-1]==0) {
curr=rek(i+c[j], j+1, 1);
if (curr) crn[i]++, crn[i+c[j]]--, ret=1;
}
return ret;
}
string solve_puzzle(string s, vector<int> cc) {
c=cc;
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, -1, sizeof dp);
memset(crn, 0, sizeof crn);
memset(bel, 0, sizeof bel);
assert(rek(1, 0, 0));
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] && s[i]=='X') assert(0);
// if (crn[i] && s[i]=='_') assert(0);
if (bel[i] && crn[i]) res+='?';
else if (crn[i]) res+='X';
else if (bel[i]) res+='_';
else assert(0);
}
return res;
}
