#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
int n;
int maxK;
vector <int > c;
#define int long long
vector< vector <int > > memo;
vector< int > pref;
vector<int> w;
vector<int> b;
vector< int > prefB;
string s;
bool dp(int position, int k){
if(k == maxK){
if(position < n){
if(s[position] == 'X') return false;
if(dp(position+1, k)){
w[position] = true;
return true;
}else{
return false;
}
}
}
if(k >= maxK) return true;
if(position >= n){
return false;
}
if(memo[position][k] != -1){
return memo[position][k];
}
memo[position][k] = 0;
if(s[position] != 'X'){
w[position] |= dp(position+1, k);
memo[position][k] |= dp(position+1, k);
}
int deb = 0;
if(position >= 1) deb = pref[position-1];
if(pref[position+c[k]-1]-deb == 0 && (position == 0 || s[position-1] != 'X') && (position+c[k] >= n || s[position+c[k]] != 'X') && position+c[k]-1 < n){
bool ok = dp(position+c[k]+1, k+1);
if(ok){
prefB[position]++;
if(position+c[k] < n) prefB[position+c[k]]--;
if(position) w[position-1] = true;
if(position+c[k] < n) w[position+c[k]] = true;
memo[position][k] |= dp(position+c[k]+1, k+1);
}
}
//cout << "DP " << position << ' ' << k << ' ' << memo[position][k] << endl;
return memo[position][k];
}
#undef int
std::string solve_puzzle(std::string S, std::vector<int> C) {
#define int long long
n = S.size();
maxK = C.size();
memo.resize(n, vector< int > (maxK));
for(int i = 0 ; i < n; i++){
for(int j = 0; j < maxK; j++){
memo[i][j] = -1;
}
}
c=C;
s = S;
prefB.resize(n,0);
pref.resize(n,0);
b.resize(n,0);
w.resize(n,0);
for(int i = 0; i<n; i++){
if(i) pref[i] += pref[i-1];
pref[i] += (s[i] == '_');
}
dp(0,0);
int curr = 0;
for(int i = 0; i < n; i++){
curr += prefB[i];
if(curr) b[i] = true;
}
string ans = "";
for(int i = 0; i < n; i++){
if(b[i] && w[i]){
ans += '?';
}else if(w[i]){
ans += '_';
}else if(b[i]){
ans += 'X';
}
}
return ans;
}
