#include "paint.h"
#include<cstdlib>
#include<iostream>
#include<vector>
#include<string>
#include<bitset>
#define DIM 200005
using namespace std;
static string sol;
static int sum[DIM], ff[DIM];
static short df[103][DIM], ds[103][DIM];
string solve_puzzle(string c, vector<int> v) {
int n, k, i, j, ok;
n = c.size();
k = v.size();
c += '0';
v.push_back(0);
for(i = n; i >= 1; i--){
c[i] = c[i - 1];
}
for(i = k; i >= 1; i--){
v[i] = v[i - 1];
}
for(i = 1; i <= n; i++){
sum[i] = sum[i - 1];
if(c[i] == '_'){
sum[i]++;
}
}
c[0] = '0';
c += '0';
df[0][0] = 1;
for(i = 0; i <= k; i++){
for(j = 1; j <= n; j++){
if(c[j] != 'X' && df[i][j - 1] == 1){
df[i][j] = 1;
}
if(j >= v[i] && sum[j] - sum[ j - v[i] ] == 0 && df[i - 1][ max(0, j - v[i] - 1) ] == 1 && c[j - v[i] ] != 'X'){
df[i][j] = 1;
}
}
}
ds[k + 1][n + 1] = 1;
v.push_back(0);
for(i = k + 1; i >= 1; i--){
for(j = n; j >= 1; j--){
if(c[j] != 'X' && ds[i][j + 1] == 1){
ds[i][j] = 1;
}
if(j + v[i] - 1 <= n && sum[j + v[i] - 1] - sum[j - 1] == 0 && ds[i + 1][ min(j + v[i] + 1, n + 1) ] == 1 && c[j + v[i] ] != 'X'){
ds[i][j] = 1;
if(df[i - 1][ max(0, j - 2) ] == 1){
ff[j]++;
ff[ j + v[i] ]--;
}
}
}
}
for(i = 1; i <= n; i++){
ff[i] += ff[i - 1];
ok = 0;
for(j = 0; j <= k; j++){
if(df[j][i - 1] == 1 && ds[j + 1][i + 1] == 1){
ok = 1;
}
}
if(c[i] == 'X'){
ok = 0;
}
if(ok == 1 && ff[i] > 0){
sol += '?';
}
else{
if(ok == 1){
sol += '_';
}
else{
sol += 'X';
}
}
}
return sol;
}
