#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n, m;
int sumwhite[N], sumf[N][105];
bool isblack[N], iswhite[N];
bool fpre[N][105], fsuf[N][105];
bool flag[N][105];
string solve_puzzle(string s, vector<int> c) {
n = s.size(), m = c.size();
for (int i = 1; i <= n; ++i) {
sumwhite[i] = sumwhite[i - 1] + (s[i - 1] == '_');
}
fpre[0][0] = fsuf[n + 1][m + 1] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
if (s[i - 1] != 'X') fpre[i][j] |= fpre[i - 1][j];
if (j >= 1 && i >= c[j - 1] && sumwhite[i] - sumwhite[i - c[j - 1]] == 0) {
if (i > c[j - 1] && s[i - c[j - 1] - 1] == 'X') continue;
fpre[i][j] |= flag[i][j] = fpre[max(0, i - c[j - 1] - 1)][j - 1];
}
}
}
for (int i = n; i >= 1; --i) {
for (int j = m + 1; j >= 1; --j) {
if (s[i - 1] != 'X') fsuf[i][j] |= fsuf[i + 1][j];
if (j <= m && n - i + 1 >= c[j - 1] && sumwhite[i + c[j - 1] - 1] - sumwhite[i - 1] == 0) {
if (n - i + 1 > c[j - 1] && s[i + c[j - 1] - 1] == 'X') continue;
fsuf[i][j] |= fsuf[min(n + 1, i + c[j - 1] + 1)][j + 1];
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (i == n) {
sumf[i][j] = sumf[i - 1][j] + (flag[i][j] && j == m);
}
else {
sumf[i][j] = sumf[i - 1][j] + (flag[i][j] && s[i] != 'X' && fsuf[i + 2][j + 1]);
}
}
}
for (int i = 1; i <= n; ++i) {
isblack[i] = s[i - 1] == 'X';
iswhite[i] = s[i - 1] == '_';
}
for (int i = 1; i <= n; ++i) {
if (s[i - 1] != '.') continue;
for (int j = 0; j <= m; ++j) {
if (fpre[i - 1][j] && fsuf[i + 1][j + 1]) iswhite[i] = 1;
}
for (int j = 1; j <= m; ++j) {
if (sumf[min(n, i + c[j - 1] - 1)][j] - sumf[i - 1][j]) isblack[i] = 1;
}
}
string res;
for (int i = 1; i <= n; ++i) {
if (isblack[i] && iswhite[i]) res.push_back('?');
else if (iswhite[i]) res.push_back('_');
else res.push_back('X');
}
return res;
}
