#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5;
const int K = 1e2;
int n, k;
int x[K+5], b[N+5], w[N+5];
int memo[N+5][K+5], vis[N+5][K+5];
string a;
set<int> st;
bool white(int l, int r) {
if (st.empty()) return 0;
auto it = st.lower_bound(l);
if (it != st.end() && *it <= r) return 1;
return 0;
}
int dp(int pos, int id) {
if (pos >= n) return (id == k);
if (memo[pos][id] != -1) return memo[pos][id];
int ret = 0;
if (a[pos] != 'X') ret |= dp(pos+1,id);
if (pos+x[id]-1 < n && id < k && !white(pos,pos+x[id]-1) && a[pos+x[id]] != 'X') {
ret |= dp(pos+x[id]+1,id+1);
}
// cout << ">> " << pos << ' ' << id << " -> " << ret << '\n';
return memo[pos][id] = ret;
}
void bt(int pos, int id) {
if (pos >= n || vis[pos][id]) return;
vis[pos][id] = 1;
if (a[pos] != 'X' && dp(pos+1,id)) {
w[pos] = 1;
bt(pos+1,id);
}
if (pos+x[id]-1 < n && id < k && !white(pos,pos+x[id]-1) && a[pos+x[id]] != 'X' && dp(pos+x[id]+1,id+1)) {
b[pos]++; b[pos+x[id]]--;
w[pos+x[id]] = 1;
bt(pos+x[id]+1,id+1);
}
}
string solve_puzzle(string s, vector<int> c) {
n = s.length(); k = c.size(); a = s;
for (int i = 0; i < n; i++) {
if (s[i] == '_') st.insert(i);
}
for (int i = 0; i < k; i++) x[i] = c[i];
memset(memo,-1,sizeof(memo));
bt(0,0);
string ans;
int cur = 0;
for (int i = 0; i < n; i++) {
cur += b[i];
if (w[i] && cur) ans += '?';
else ans += (w[i] ? '_' : 'X');
}
return ans;
}
