#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 + 1;
if (i < n && s[i] == '_') r[i] = i;
}
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 (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;
}
}
dp2[n][m][1] = 1;
for (int i = n; i >= 1; i--) {
for (int j = m; j >= 0; j--) {
if (!dp2[i][j][0] && !dp2[i][j][1]) continue;
//cout << dp2[i][j][0] << ' ' << dp2[i][j][1] << ' ' << l[i] << " ";
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;
}
}
int mx = -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (r[i] >= i + c[j] && i + c[j] <= n) {
if (dp1[i][j][1] && dp2[i + c[j]][j + 1][1]) mx = max(mx, i + c[j] - 1);
}
}
if (s[i] != '.') {
ans += s[i];
continue;
}
int y = 0;
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 (mx >= i && y) ans += '?';
else if (mx >= i) ans += 'X';
else ans += '_';
}
return ans;
}
