#include <bits/stdc++.h>
#include "paint.h"
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
const int MAX_N = 2e5 + 5;
const int MAX_K = 105;
bool dp[MAX_N][MAX_K];
int add_x[MAX_N];
int add_empty[MAX_N];
int nexts[MAX_N];
bool visited[MAX_N][MAX_K];
int ex;
vi c;
string s;
void Solve(int i, int j) {
if (i < 0 || j < 0 || visited[i][j]) return;
visited[i][j] = true;
if (s[i] != 'X' && i && dp[i - 1][j]) {
add_empty[i]++;
add_empty[i + 1]--;
Solve(i - 1, j);
}
int last = i - c[j];
bool b = nexts[last + 1] > i && (last < 0 || s[last] != 'X');
if (b && !j && ex > last) {
add_x[last + 1]++, add_x[i + 1]--;
add_empty[0]++, add_empty[last + 1]--;
} else if (b && j && dp[last - 1][j - 1]) {
add_x[last + 1]++, add_x[i + 1]--;
add_empty[last]++, add_empty[last + 1]--;
Solve(last - 1, j - 1);
}
}
int n, k;
string solve_puzzle(string S, vi C) {
s = S, c = C;
n = s.size(), k = c.size();
nexts[n] = n;
ex = n;
for (int i = n - 1; i >= 0; i--) {
nexts[i] = (s[i] == '_' ? i : nexts[i + 1]);
if (s[i] == 'X') ex = i;
}
for (int i = 0; i < n; i++) {
if (s[i] != 'X' && i) {
for (int j = 0; j < k; j++) {
dp[i][j] = dp[i - 1][j];
}
}
if (s[i] == '_') continue;
for (int j = 0, sum = -1; j < k; j++) {
sum += c[j] + 1;
if (sum > i + 1) break;
if (dp[i][j]) continue;
int last = i - c[j];
bool b = nexts[last + 1] > i && (last < 0 || s[last] != 'X');
if (b && !j) {
dp[i][j] = ex > last;
} else if (b && dp[last - 1][j - 1]) {
dp[i][j] = true;
}
}
}
Solve(n - 1, k - 1);
string ans(n, '?');
for (int i = 0, x = 0, em = 0; i < n; i++) {
x += add_x[i], em += add_empty[i];
if (x && !em) ans[i] = 'X';
else if (!x && em) ans[i] = '_';
}
return ans;
}
