#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
const int N = 200 * 1000 + 5, K = 105;
bool dp[N][K][3];
vector <pair <int, pair <int, int> > > adj[N][K][3];
bool mark[N][K][3];
int e[N];
bool ans1[N];
void dfs(int x, int y, int z) {
if (mark[x][y][z]) {
return;
}
mark[x][y][z] = true;
for (auto p : adj[x][y][z]) {
dfs(p.first, p.second.first, p.second.second);
}
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
string ans = "";
int n = s.size(), k = c.size();
dp[0][0][0] = true;
int lt = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
if (s[i - 1] != 'X') {
if (dp[i - 1][j][0]) {
dp[i][j][0] = true;
adj[i][j][0].push_back({i - 1, {j, 0}});
}
if (dp[i - 1][j][1]) {
dp[i][j][0] = true;
adj[i][j][0].push_back({i - 1, {j, 1}});
}
}
if (j && s[i - 1] != '_') {
int x = c[j - 1];
if (dp[i - x][j - 1][0] && lt <= i - x) {
dp[i][j][1] = true;
adj[i][j][1].push_back({i - x, {j - 1, 0}});
}
}
if (s[i - 1] == '_') {
lt = i;
}
}
}
if (dp[n][k][0]) {
dfs(n, k, 0);
}
if (dp[n][k][1]) {
dfs(n, k, 1);
}
int cnt = 0;
for (int i = n; i > 0; i--) {
cnt -= e[i];
for (int j = 1; j <= k; j++) {
if (mark[i][j][1]) {
cnt++;
e[i - c[j - 1]]++;
}
}
// cout << "72 " << i << " " << cnt << endl;
if (cnt > 0) {
ans1[i] = true;
}
}
for (int i = 1; i <= n; i++) {
bool b = false;
for (int j = 0; j <= k; j++) {
if (mark[i][j][0]) {
b = true;
}
}
if (b) {
if (ans1[i]) {
ans += '?';
}
else {
ans += '_';
}
}
else {
ans += 'X';
}
}
return ans;
}
