#include "paint.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
string solve_puzzle (string s, vector <int> c) {
int n = s.length(), k = c.size();
c.insert(c.begin(), 0);
c.push_back(0);
vector <vector <int>> p(2, vector <int> (n + 2, 0));
vector <vector <int>> h(2, vector <int> (n + 2, 0));
vector <vector <int>> f(k + 2, vector <int> (n + 2, 0));
vector <vector <int>> g(k + 2, vector <int> (n + 2, 0));
for (int i = 0; i < n; i++) {
if (s[i] == '_') p[0][i + 1]++;
if (s[i] == 'X') p[1][i + 1]++;
}
for (int i = 1; i <= n + 1; i++) {
p[0][i] += p[0][i - 1];
p[1][i] += p[1][i - 1];
}
f[0][0] = 1;
for (int i = 1; i <= k; i++) {
for (int j = c[i]; j <= n; j++) {
if (p[0][j] - p[0][j - c[i]] != 0) {
continue;
}
if (j - c[i] == 0) {
f[i][j] |= f[i - 1][0];
continue;
}
for (int l = j - c[i]; l >= 1; l--) {
if (p[1][j - c[i]] - p[1][l - 1] != 0) {
break;
}
f[i][j] |= f[i - 1][l - 1];
}
}
}
g[k + 1][n + 1] = 1;
for (int i = k; i >= 1; i--) {
for (int j = n - c[i] + 1; j >= 1; j--) {
if (p[0][j + c[i] - 1] - p[0][j - 1] != 0) {
continue;
}
if (j + c[i] == n + 1) {
g[i][j] |= g[i + 1][n + 1];
continue;
}
for (int l = j + c[i]; l <= n; l++) {
if (p[1][l] - p[1][j + c[i] - 1] != 0) {
break;
}
g[i][j] |= g[i + 1][l + 1];
}
}
}
for (int l = 0; l <= k; l++) {
for (int i = 0; i <= n; i++) {
for (int j = i + 2; j <= n + 1; j++) {
if (f[l][i] && g[l + 1][j] && p[1][j - 1] - p[1][i] == 0) {
h[0][i + 1]++; h[0][j]--;
h[1][i - c[l] + 1]++; h[1][i + 1]--;
h[1][j]++; h[1][j + c[l + 1]]--;
}
}
}
}
for (int i = 1; i <= n + 1; i++) {
h[0][i] += h[0][i - 1];
h[1][i] += h[1][i - 1];
}
string ans;
for (int i = 1; i <= n; i++) {
if (h[0][i] && h[1][i]) {
ans.push_back('?');
} else if (h[0][i]) {
ans.push_back('_');
} else {
ans.push_back('X');
}
}
return ans;
}
