#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
string solve_puzzle(string s, vector<int> c) {
int n = (int) s.size();
int m = (int) c.size();
s = "X_" + s + "_X";
c.insert(c.begin(), 1);
c.emplace_back(1);
n += 4;
m += 2;
vector<int> pref(n + 1);
for (int i = 0; i < n; i++) {
pref[i + 1] = pref[i] + (s[i] == '_');
}
vector<vector<int>> left(m, vector<int>(n));
left[0][0] = 1;
for (int i = 0; i < m; i++) {
if (i != 0) {
for (int j = 1; j + c[i] - 1 < n; j++) {
if (s[j - 1] != 'X' && (j + c[i] == n || s[j + c[i]] != 'X') && pref[j] == pref[j + c[i]]) {
left[i][j + c[i] - 1] |= left[i - 1][j - 2];
}
}
}
for (int j = 1; j < n; j++) {
if (s[j] != 'X') {
left[i][j] |= left[i][j - 1];
}
}
}
vector<vector<int>> right(m, vector<int>(n));
right[m - 1][n - 1] = 1;
for (int i = m - 1; i >= 0; i--) {
if (i != m - 1) {
for (int j = n - 2; j - c[i] + 1 >= 0; j--) {
if (s[j + 1] != 'X' && (j - c[i] == -1 || s[j - c[i]] != 'X') && pref[j - c[i] + 1] == pref[j + 1]) {
right[i][j - c[i] + 1] |= right[i + 1][j + 2];
}
}
}
for (int j = n - 2; j >= 0; j--) {
if (s[j] != 'X') {
right[i][j] |= right[i][j + 1];
}
}
}
vector<int> black(n + 1);
vector<int> white(n + 1);
for (int i = 1; i < m; i++) {
for (int j = 2; j < n - 2; j++) {
if (left[i - 1][j - 1] && right[i][j + 1] && s[j] != 'X') {
white[j] = 1;
}
}
}
for (int i = 1; i < m - 1; i++) {
for (int j = 2; j + c[i] <= n - 2; j++) {
if (s[j - 1] == 'X' || s[j + c[i]] == 'X' || pref[j] != pref[j + c[i]]) {
continue;
}
if (left[i - 1][j - 2] && right[i + 1][j + c[i] + 1]) {
black[j]++;
black[j + c[i]]--;
}
}
}
for (int i = 0; i < n; i++) {
black[i + 1] += black[i];
}
string res;
for (int i = 2; i < n - 2; i++) {
if (black[i] && white[i]) {
res += "?";
} else if (black[i]) {
res += "X";
} else if (white[i]) {
res += "_";
} else {
res += "!";
}
}
return res;
}
#ifdef tabr
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
debug(solve_puzzle("..........", {3, 4}));
debug(solve_puzzle("........", {3, 4}));
debug(solve_puzzle("..._._....", {3}));
debug(solve_puzzle(".X........", {3}));
debug(solve_puzzle("....X..X...", {3, 3}));
debug(solve_puzzle("..X_.._X...", {1, 2, 1}));
debug(solve_puzzle(".._.X_.._.._X.", {2, 2, 2}));
debug(solve_puzzle("..X_.._X....", {1, 2, 2}));
debug(solve_puzzle(".X.._.......", {1, 2, 3}));
return 0;
}
#endif
