#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
using si = short int;
const int N = 2e5+10;
const int K = 105;
int n, sum[N], can[N], sz[K], Xcnt[N];
string s;
si dp[2][K][N];
int res[2][N];
si DP(int prev, int blc, int pos) {
if(blc < 0) {
if(pos < 1) return 1;
if(Xcnt[pos] == 0) {
res[0][1]++;
res[0][pos + 1]--;
return 1;
}
return 0;
}
if(pos < 1) return 0;
si &ret = dp[prev][blc][pos];
if(ret != -1) return ret;
if(s[pos] == 'X') {
if(prev == 0) {
if(pos - sz[blc] < 0 || sum[pos] - sum[pos - sz[blc]] > 0) return ret = 0;
si got = DP(1, blc - 1, pos - sz[blc]);
if(got == 1) {
res[1][pos - sz[blc] + 1]++;
res[1][pos + 1]--;
}
return ret = got;
}
return ret = 0;
}
if(s[pos] == '_') {
si got = DP(0, blc, pos - 1);
if(got == 1) {
res[0][pos]++;
res[0][pos + 1]--;
}
return ret = got;
}
si zero = DP(0, blc, pos - 1);
if(zero == 1) {
res[0][pos]++;
res[0][pos + 1]--;
}
si one;
if(prev == 1 || pos - sz[blc] < 0 || sum[pos] - sum[pos - sz[blc]] > 0) one = 0;
else {
one = DP(1, blc - 1, pos - sz[blc]);
if(one == 1) {
res[1][pos - sz[blc] + 1]++;
res[1][pos + 1]--;
}
}
return ret = (one | zero);
}
string solve_puzzle(string _s, vector<int> c) {
s = "#" + _s; n = s.size();
for(int i = 0; i < (int)c.size(); i++)
sz[i] = c[i];
for(int i = 1; i < n; i++) {
sum[i] = sum[i - 1] + (s[i] == '_');
Xcnt[i] = Xcnt[i - 1] + (s[i] == 'X');
}
memset(dp, -1, sizeof dp);
DP(0, (int)c.size() - 1, n - 1);
for(int i = 1; i < n; i++) {
res[0][i] += res[0][i - 1];
res[1][i] += res[1][i - 1];
if(res[0][i] && res[1][i]) _s[i - 1] = '?';
else if(res[0][i]) _s[i - 1] = '_';
else _s[i - 1] = 'X';
}
return _s;
}
