#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string str, ans;
vector<int> a;
int pt[101], prv[101], cnt[101], N, K, X, cntx;
bool valid(int x, int y){
return ((x-1<0 || str[x-1]!='X') && (y>=N || str[y]!='X'));
}
void update(int x, int y, int l, int mx = 1e9){
if (x==y) return;
for (int i=max(x+l, y);i<y+l;i++) if (i<mx) ans[i] = '?';
for (int i=x;i<min(x+l, y);i++) if (i<mx){
if (ans[i]=='X') ans[i] = 'X';
else ans[i] = '?';
}
}
bool init(int pos, int t){
for (int i=pt[t]-1;i>=pos;i--){
//if (t==1) printf("%d %d %c\n", i, cnt[t], str[i]);
pt[t] = i;
if (str[i]=='X') cntx++;
if (str[i]=='_') cnt[t]++;
if (i+a[t]>N) continue;
if (!cnt[t] && valid(i, i+a[t])){
if ((t==K-1 || init(i+a[t]+1, t+1)) && cntx==X) return 1;
}
if (i>=pos){
if (str[i+a[t]-1]=='_') cnt[t]--;
if (str[i+a[t]-1]=='X') cntx--;
}
}
return 0;
}
bool solve(int pos, int t){
//cout << pos << ' ' << t << ' ' << ans << '\n';
if (pos!=prv[t]){
assert(prv[t]-pos==1);
if (str[pos+a[t]]=='_') cnt[t]--;
if (str[pos+a[t]]=='X') cntx--;
if (str[pos]=='_') cnt[t]++;
if (str[pos]=='X') cntx++;
}
prv[t] = pos;
if (!cnt[t] && valid(pos, pos+a[t])){
bool ret = 0;
if (cntx==X){
update(pos, pt[t], a[t]);
ret = 1;
}
if (t<K-1){
for (int i=prv[t+1];i>=pos+a[t]+1;i--) if (solve(i, t+1)){
if (!ret) update(pos, pt[t], a[t], i);
ret = 1;
}
}
if (ret) pt[t] = pos;
return ret;
}
return 0;
}
string solve_puzzle(string s, vector<int> c) {
str = s, a = c, N = s.size(), K = c.size();
ans.resize(s.size());
fill(pt, pt+K, N);
for (int i=0;i<N;i++) if (str[i]=='X') X++;
assert(init(0, 0));
fill(ans.begin(), ans.end(), '_');
for (int i=0;i<K;i++) fill(ans.begin()+pt[i], ans.begin()+pt[i]+a[i], 'X');
//cout << ans << '\n';
for (int i=0;i<K;i++) prv[i] = pt[i];
for (int i=pt[0];i>=0;i--) solve(i, 0);
return ans;
}
