#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();
vector<vector<int>> a(2, vector<int>(m));
for (int z = 0; z < 2; z++) {
vector<int> pref(n + 1);
for (int i = 0; i < n; i++) {
pref[i + 1] = pref[i] + (s[i] == '_');
}
vector<vector<int>> dp(m, vector<int>(n, n));
for (int i = 0; i < m; i++) {
int lst = -1;
for (int j = 0; j + c[i] <= n; j++) {
if (j > 0 && s[j - 1] == 'X') {
if (i == 0) {
break;
}
lst = j - 1;
continue;
}
if (j + c[i] < n && s[j + c[i]] == 'X') {
continue;
}
if (pref[j] != pref[j + c[i]]) {
continue;
}
debug(i, j);
if (i == 0) {
dp[i][j] = -1;
} else {
for (int l = 0; l + c[i - 1] < j; l++) {
if (dp[i - 1][l] < n && lst < l + c[i - 1]) {
dp[i][j] = l;
break;
}
}
}
}
}
debug(dp);
int lst = -1;
for (int i = n - 1; i >= 0; i--) {
if (s[i] == 'X') {
lst = i;
break;
}
}
int pos = -1;
for (int i = 0; i < n; i++) {
if (dp[m - 1][i] < n && lst < i + c[m - 1]) {
pos = i;
break;
}
}
debug(pos);
for (int i = m - 1; i >= 0; i--) {
a[z][i] = pos;
pos = dp[i][pos];
}
reverse(s.begin(), s.end());
reverse(c.begin(), c.end());
}
reverse(a[1].begin(), a[1].end());
for (int i = 0; i < m; i++) {
a[1][i] = n - 1 - a[1][i];
}
debug(a);
for (int i = 0; i < m; i++) {
for (int j = a[1][i] - c[i] + 1; j <= a[0][i] + c[i] - 1; j++) {
s[j] = 'X';
}
}
vector<int> pref(n + 1);
for (int i = 0; i < n; i++) {
pref[i + 1] = pref[i] + (s[i] == '_');
}
vector<int> sum(n + 1);
for (int i = 0; i < m; i++) {
for (int j = 0; j + c[i] <= n; j++) {
if (j > 0 && s[j - 1] == 'X') {
continue;
}
if (j + c[i] < n && s[j + c[i]] == 'X') {
continue;
}
if (pref[j] != pref[j + c[i]]) {
continue;
}
if (a[0][i] <= j && j + c[i] - 1 <= a[1][i]) {
sum[j]++;
sum[j + c[i]]--;
}
}
}
for (int i = 0; i < n; i++) {
sum[i + 1] += sum[i];
if (s[i] == '.') {
s[i] = (sum[i] > 0 ? '?' : '_');
}
}
return s;
}
#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}));
return 0;
}
#endif
