#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#include <cstdlib>
int N, K;
bool f[101][200004], g[101][200004];
int ps[2][200004];
int ok[2][200004];
std::string solve_puzzle(std::string s, std::vector<int> c) {
N = s.size();
s = "__" + s + "__";
K = c.size();
f[0][0] = f[0][1] = g[0][N + 2] = g[0][N + 3] = 1;
for (int i = 2; i <= N + 1; i++) ps[0][i] = ps[0][i - 1] + (s[i] == '_');
for (int i = 2; i <= N + 1; i++) ps[1][i] = ps[1][i - 1] + (s[i] == 'X');
for (int i = 2; i <= N + 1; i++) {
for (int j = 0; j <= K; j++) {
if (s[i] == 'X' || s[i] == '.') {
if (j > 0 && i - 1 >= c[j - 1] && ps[0][i] - ps[0][i - c[j - 1]] == 0 && s[i - c[j - 1]] != 'X' && s[i + 1] != 'X') {
f[j][i] |= f[j - 1][i - c[j - 1] - 1];
}
}
if (s[i] == '_' || s[i] == '.') {
f[j][i] |= f[j][i - 1];
}
}
}
reverse(c.begin(), c.end());
for (int i = N + 1; i >= 2; i--) {
for (int j = 0; j <= K; j++) {
if (s[i] == 'X' || s[i] == '.') {
if (j > 0 && i + c[j - 1] - 1 <= N + 1 && ps[0][i + c[j - 1] - 1] - ps[0][i - 1] == 0 && s[i + c[j - 1]] != 'X' && s[i - 1] != 'X') {
g[j][i] |= g[j - 1][i + c[j - 1] + 1];
}
}
if (s[i] == '_' || s[i] == '.') {
g[j][i] |= g[j][i + 1];
}
}
}
reverse(c.begin(), c.end());
for (int i = 2; i <= N + 1; i++) {
for (int j = 0; j <= K; j++) {
if (s[i] == 'X') continue;
if (f[j][i - 1] && g[K - j][i + 1]) ok[0][i] = 1;
}
}
for (int j = 1; j <= K; j++) {
for (int i = c[j - 1] + 1; i <= N + 1; i++) {
if (ps[0][i] - ps[0][i - c[j - 1]]) continue;
if (s[i + 1] == 'X') continue;
if (s[i - c[j - 1]] == 'X') continue;
if (f[j - 1][i - c[j - 1] - 1] && g[K - j][i + 2]) ok[1][i - c[j - 1] + 1]++, ok[1][i + 1]--;
}
}
for (int i = 1; i <= N + 1; i++) ok[1][i] += ok[1][i - 1];
string ans(N, '?');
for (int i = 2; i <= N + 1; i++) {
if (ok[1][i]) ans[i - 2] = 'X';
if (ok[0][i]) ans[i - 2] = '_';
if (ok[1][i] && ok[0][i]) ans[i - 2] = '?';
}
return ans;
}
