#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef GUDEB
#define D(x) cerr << #x << ": " << (x) << '\n';
#define ifdeb if(true)
#else
#define D(x) ;
#define ifdeb if(false)
#endif
#define all(x) begin(x), end(x)
using ull = unsigned long long;
using ll = long long;
char dpl[200001][101];
char dpr[200001][101];
int ups[200001];
bool ugd[200000];
int dxgd[200001];
int xgd[200000];
std::string solve_puzzle(string s, vector<int> c) {
D(s)
int n = s.size();
int k = c.size();
ups[0] = 0;
for(int i = 0; i < n; ++i) {
ups[i+1] = ups[i] + (s[i] == '_');
}
dpl[0][0] = 2;
for(int i = 0; i < n; ++i) {
for(int j = 0; j <= k; ++j) {
if(!dpl[i][j]) continue;
if(dpl[i][j] == 2 && j < k && i + c[j] <= n) {
if(ups[i+c[j]] - ups[i] == 0) {
if(i+c[j] == n || s[i+c[j]] != 'X') {
dpl[i+c[j]][j+1] = 1;
}
}
}
if(s[i] != 'X') {
dpl[i+1][j] = 2;
}
}
}
dpr[0][0] = 2;
for(int i = 0; i < n; ++i) {
for(int j = 0; j <= k; ++j) {
if(!dpr[i][j]) continue;
if(dpr[i][j] == 2 && j < k && i + c[k-1-j] <= n) {
if(ups[n-i] - ups[n-i-c[k-1-j]] == 0) {
if(i+c[k-1-j] == n || s[n-1-i-c[k-1-j]] != 'X') {
dpr[i+c[k-1-j]][j+1] = 1;
}
}
}
if(s[n-1-i] != 'X') {
dpr[i+1][j] = 2;
}
}
}
for(int i = 0; i < n; ++i) {
if(s[i] == 'X') continue;
for(int j = 0; j <= k; ++j) {
if(dpl[i][j] && dpr[n-1-i][k-j]) {
ugd[i] = true;
break;
}
}
}
for(int j = 0; j < k; ++j) {
for(int i = 0; i <= n-c[j]; ++i) {
if(ups[i+c[j]] - ups[i] > 0) continue;
if(dpl[i][j] == 2 && dpr[n-c[j]-i][k-j-1] == 2) {
++dxgd[i];
--dxgd[i+c[j]];
continue;
}
}
}
xgd[0] = dxgd[0];
for(int i = 1; i < n; ++i) {
xgd[i] = xgd[i-1] + dxgd[i];
}
string out;
for(int i = 0; i < n; ++i) {
if(xgd[i] && ugd[i]) {
out.push_back('?');
} else if(xgd[i]) {
out.push_back('X');
} else if(ugd[i]) {
out.push_back('_');
}
}
ifdeb {
cerr << '\n';
for(int i = 0; i <= n; ++i) {
cerr << ups[i] << ' ';
}
cerr << '\n' << '\n';
for(int i = 0; i <= n; ++i) { for(int j = 0; j <= k; ++j) {
cerr << dpl[i][j] << ' ';
}
cerr << '\n';
}
cerr << '\n';
for(int i = 0; i <= n; ++i) { for(int j = 0; j <= k; ++j) {
cerr << dpr[i][j] << ' ';
}
cerr << '\n';
}
cerr << '\n';
for(int i = 0; i < n; ++i) {
cerr << ugd[i] << ' ';
}
cerr << '\n' << '\n';
for(int i = 0; i < n; ++i) {
cerr << xgd[i] << ' ';
}
cerr << '\n' << '\n';
}
return out;
}
