#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 + 4, 0));
vector <vector <int>> h(2, vector <int> (n + 4, 0));
vector <vector <int>> f(k + 2, vector <int> (n + 4, 0));
vector <vector <int>> g(k + 2, vector <int> (n + 4, 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 = 1; j <= n + 1; j++) {
f[i - 1][j] += f[i - 1][j - 1];
}
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] != 0;
continue;
}
int L = 1, R = j - c[i], ans = -1;
while (L <= R) {
int mid = (L + R) / 2;
if (p[1][j - c[i]] - p[1][mid - 1] == 0) {
R = mid - 1; ans = mid;
} else {
L = mid + 1;
}
}
if (ans == -1) {
continue;
}
f[i][j] = (f[i - 1][j - c[i] - 1] - (ans <= 1 ? 0 : f[i - 1][ans - 2])) != 0;
}
}
for (int j = 1; j <= n + 1; j++) {
f[k][j] += f[k][j - 1];
}
g[k + 1][n + 1] = 1;
for (int i = k; i >= 1; i--) {
for (int j = n; j >= 1; j--) {
g[i + 1][j] += g[i + 1][j + 1];
}
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;
}
int L = j + c[i], R = n, ans = -1;
while (L <= R) {
int mid = (L + R) / 2;
if (p[1][mid] - p[1][j + c[i] - 1] == 0) {
L = mid + 1; ans = mid;
} else {
R = mid - 1;
}
}
if (ans == -1) {
continue;
}
g[i][j] = (g[i + 1][j + c[i] + 1] - (ans >= n ? 0 : g[i + 1][ans + 2])) != 0;
}
}
for (int i = n; i >= 1; i--) {
g[1][i] += g[1][i + 1];
}
for (int l = 0; l <= k; l++) {
for (int i = 0; i <= n; i++) {
if (!f[l][i] - (i == 0 ? 0 : f[l][i - 1])) {
continue;
}
int L = i + 2, R = n + 1, ans = -1;
while (L <= R) {
int mid = (L + R) / 2;
if (p[1][mid - 1] - p[1][i] == 0) {
L = mid + 1; ans = mid;
} else {
R = mid - 1;
}
}
if (ans == -1) {
continue;
}
L = i + 2, R = ans; int ans2 = -1;
while (L <= R) {
int mid = (L + R) / 2;
if (g[l + 1][mid] - g[l + 1][ans + 1]) {
L = mid + 1; ans2 = mid;
} else {
R = mid - 1;
}
}
if (ans2 == -1) {
continue;
}
L = i + 2, R = ans2; int ans3 = -1;
while (L <= R) {
int mid = (L + R) / 2;
if (g[l + 1][i + 2] - g[l + 1][mid + 1]) {
R = mid - 1; ans3 = mid;
} else {
L = mid + 1;
}
}
h[0][i + 1]++; h[0][ans2]--;
h[1][i - c[l] + 1]++; h[1][i + 1]--;
h[1][ans3]++; h[1][ans2 + 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;
}
