#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
const int maxk = 105;
int memo[maxn][maxk];
string ans, A;
vector<int> seg;
int suf[maxn], isi[maxn], kosong[maxn];
int N, K;
int dp(int idx, int left) {
// cout << idx << " " << left << '\n';
if(idx > N) return 0;
if(idx == N) return left == K;
if(memo[idx][left] != -1) return memo[idx][left];
int res = 0;
if(A[idx] != 'X')
res = res || dp(idx + 1, left);
if(left < K && seg[left] <= suf[idx] && A[idx + seg[left]] != 'X') {
if(idx + seg[left] + 1 <= N){
res = res || dp(idx + seg[left] + 1, left + 1);
}else {
res = res || dp(idx + seg[left], left + 1);
}
}
return memo[idx][left] = res;
}
void search(int idx, int left) {
if(left == K && idx == N)return;
if(A[idx] != 'X' && dp(idx + 1, left)) {
kosong[idx] = 1;
search(idx + 1, left);
}
if(left < K && seg[left] <= suf[idx] && A[idx + seg[left]] != 'X' && dp(idx + seg[left] + (idx + seg[left] + 1 <= N), left + 1)) {
isi[idx]++;
isi[idx + seg[left]]--;
kosong[idx + seg[left]] = 1;
search(idx + seg[left] + 1, left + 1);
}
}
string solve_puzzle(string s, vector<int> c) {
A = s; seg = c;
N = s.size(); K = c.size();
// cout << N << " " << K << "\n";
for(int i = N - 1; i >= 0; i--) {
suf[i] = (A[i] == '_' ? 0 : 1 + suf[i + 1]);
}
memset(memo, -1, sizeof(memo));
dp(0, 0);
search(0, 0);
int state = 0;
ans.resize(N);
for(int i = 0; i < N; i++) {
state += isi[i];
if(kosong[i] && state > 0) {
ans[i] = '?';
}else if(kosong[i]) {
ans[i] = '_';
}else if(state > 0) {
ans[i] = 'X';
}
}
return ans;
}
