#include "paint.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); i++)
#define rrep(i, n) for(ll i = ll(n)-1; i >= 0; i--)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
bool dpl[200010][110][2];
bool dpr[200010][110][2];
string solve_puzzle(string s, vi c) {
int n = s.size();
int K = c.size();
rep(_, 2) {
vi wh(n + 1);
rep(i, n) wh[i + 1] = wh[i] + (s[i] == '_');
dpl[0][0][1] = true;
rep(i, n) rep(j, K + 1) rep(k, 2) {
if (!dpl[i][j][k]) continue;
if (s[i] != 'X') dpl[i + 1][j][1] = true;
if (k and j < K and i + c[j] <= n and wh[i + c[j]] == wh[i]) {
dpl[i + c[j]][j + 1][0] = true;
}
}
reverse(all(s));
reverse(all(c));
swap(dpl, dpr);
}
// rep(i, n + 1) rep(j, K + 1) rep(k, 2) {
// cout << i << ' ' << j << ' ' << k << ' ' << dpl[i][j][k] << endl;
// cout << i << ' ' << j << ' ' << k << ' ' << dpr[i][j][k] << endl;
// }
vvi sum(K, vi(2 * n));
rep(i, K) rep(j, 2 * n - 1) {
int now = 0;
if (j < n) {
now = dpl[j + 1][i + 1][0] and dpr[n - j - 1][K - i - 1][1];
}
sum[i][j + 1] = sum[i][j] + now;
}
string ans = s;
rep(i, n) {
if (s[i] != '.') continue;
bool b = false, w = false;
rep(j, K + 1) {
if (!dpl[i][j][0] and !dpl[i][j][1]) continue;
if (!dpr[n - 1 - i][K - j][0] and !dpr[n - 1 - i][K - j][1]) continue;
// cout << i << ' ' << j << endl;
w = true;
}
rep(j, K) {
if (sum[j][i + c[j]] - sum[j][i]) b = true;
}
assert(b or w);
if (b and w) ans[i] = '?';
else if (b) ans[i] = 'X';
else ans[i] = '_';
}
return ans;
}
