#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define rall(s) s.rbegin(), s.rend()
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define s second
#define f first
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int N = 2e5 + 5;
bool dp1[N][101][2], dp2[N][101][2];
string solve_puzzle(string s, vector<int> c) {
string ans = "";
int n = sz(s), m = sz(c);
int l[n + 1], r[n + 1];
for (int i = 0; i <= n; i++) {
if (i) l[i] = l[i - 1];
else l[i] = -1;
if (i < n && s[i] == '_') l[i] = i;
}
for (int i = n; i >= 0; i--) {
if (i < n - 1) r[i] = r[i + 1];
else r[i] = n;
if (i < n && s[i] == '_') r[i] = i;
}
int l1[n + 1], r1[n + 1];
for (int i = 0; i <= n; i++) {
if (i) l1[i] = l1[i - 1];
else l1[i] = -1;
if (i < n && s[i] == 'X') l1[i] = i;
}
for (int i = n; i >= 0; i--) {
if (i < n) r1[i] = r1[i + 1];
else r1[i] = n;
if (i < n && s[i] == 'X') r1[i] = i;
}
vector<int> posl(m + 1, n + 1);
dp1[0][0][1] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= m; j++) {
if (!dp1[i][j][0] && !dp1[i][j][1]) continue;
if (dp1[i][j][0]) posl[j] = min(posl[j], i + 1);
if (dp1[i][j][1]) posl[j] = min(posl[j], i);
if (s[i] != 'X') dp1[i + 1][j][1] = 1;
if (dp1[i][j][1] && j < m && i + c[j] <= n && r[i] >= i + c[j]) dp1[i + c[j]][j + 1][0] = 1;
}
}
vector<int> posr(m + 1, -1);
dp2[n][m][1] = 1;
for (int i = n; i >= 1; i--) {
for (int j = m; j >= 0; j--) {
//cout << dp2[i][j][0] << ' ' << dp2[i][j][1] << ' ' << l[i] << " ";
if (!dp2[i][j][0] && !dp2[i][j][1]) continue;
if (dp2[i][j][0]) {
posr[j] = max(posr[j], i - 2);
}
if (dp2[i][j][1]) posr[j] = max(posr[j], i - 1);
if (s[i - 1] != 'X') dp2[i - 1][j][1] = 1;
if (dp2[i][j][1] && j && i - c[j - 1] >= 0 && l[i] < i - c[j - 1]) dp2[i - c[j - 1]][j - 1][0] = 1;
}
}
for (int i = 0; i < n; i++) {
if (s[i] != '.') {
ans += s[i];
continue;
}
int x = 0, y = 0;
for (int j = 0; j < m; j++) {
int tl = max(posl[j], l[i] + 1);
int tr = min(posr[j + 1], r[i] - 1);
if (tl <= i && i <= tr && tr - tl + 1 >= c[j]) {
tl = min(r1[tl], i);
tr = max(l1[tr], i);
if (tr - tl + 1 <= c[j]) x = 1;
}
}
for (int j = 0; j <= m; j++) {
if ((dp1[i][j][0] || dp1[i][j][1]) && (dp2[i + 1][j][0] || dp2[i + 1][j][1])) y = 1;
}
if (x && y) ans += '?';
else if (x) ans += 'X';
else ans += '_';
}
return ans;
}
