#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
const int mxn = 2e5 + 5, mxk = 1e2 + 5;
bool pref[mxn][mxk][2];
bool suf[mxn][mxk][2];
string solve_puzzle(string s, vector<int> c) {
int n = s.size();
int k = c.size();
s = ' ' + s;
pref[0][0][0] = true;
for (int i = 1; i <= n; ++i){
for (int j = 0; j <= k; ++j) {
if (s[i] == '.' || s[i] == '_') pref[i][j][0] = pref[i-1][j][0] || pref[i-1][j][1];
if (s[i] == 'X' || s[i] == '.') {
if (j == 0) continue;
bool flag = true;
for (int l = i - c[j-1] + 1; l <= i; ++l){
if (l <= 0 || s[l] == '_') flag = false;
}
if (!flag || !pref[i - c[j-1]][j-1][0]) continue;
pref[i][j][1] = true;
}
}
}
suf[n+1][k+1][0] = true;
for (int i = n; i >= 1; --i){
for (int j = k+1; j >= 1; --j) {
if (s[i] == '.' || s[i] == '_') suf[i][j][0] = suf[i+1][j][0] || suf[i+1][j][1];
if (s[i] == 'X' || s[i] == '.') {
if (j == k+1) continue;
bool flag = true;
for (int l = i; l < i + c[j-1]; ++l){
if (l > n || s[l] == '_') flag = false;
}
if (!flag || !suf[i + c[j-1]][j+1][0]) continue;
suf[i][j][1] = true;
}
}
}
vector<bool> posb(n+1), posw(n+1);
for (int i = 1; i <= n; ++i){
if (s[i] == 'X') continue;
for (int j = 0; j <= k; ++j) {
posw[i] = posw[i] || ((pref[i-1][j][1] || pref[i-1][j][0]) && (suf[i+1][j+1][1] || suf[i+1][j+1][0]));
}
}
for (int j = 1; j <= k; ++j){
for (int i = 1; i <= n; ++i) {
if (!pref[i-1][j-1][0] || !suf[i + c[j-1]][j+1][0]) continue;
bool flag = true;
for (int l = i; l < i + c[j-1]; ++l) {
if (s[l] == '_') flag = false;
}
if (!flag) continue;
for (int l = i; l < i + c[j-1]; ++l){
posb[l] = true;
}
}
}
string res;
for (int i = 1; i <= n; ++i){
if (posw[i] && posb[i]) res.push_back('?');
else if (posw[i]) res.push_back('_');
else res.push_back('X');
}
return res;
}
