#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define trav(a,x) for(auto&a:x)
#define all(x) x.begin(),x.end()
#define sz(x) x.size()
#define pb push_back
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
ll n,k;
vll nxt_white,blocks;
string colors;
vll sweep[2];
vector<vll> memo;
ll dp(ll pos,ll block) {
if(pos==n) {
//cout<<"pos = "<<pos<<" block = "<<block<<endl;
return block==k;
}
ll&ans=memo[pos][block];
if(ans!=-1) return ans;
ans=0;
if(colors[pos]!='X') { // color white
ll res=dp(pos+1,block);
if(res==1) {
ans=1;
++sweep[0][pos];
--sweep[0][pos+1];
}
}
if(colors[pos]=='X'&&block==k) ans=0;
if(colors[pos]!='_'&&block<k) { // color black
ll npos=pos+blocks[block];
//if(pos>=4&&block==1) cout<<"bla pos = "<<pos<<" block = "<<block<<endl;
if(npos<=nxt_white[pos]) {
if(npos==n||colors[npos]!='X') {
ll res=dp(min(npos+1,n),block+1);
if(res) {
ans=1;
++sweep[1][pos];
--sweep[1][npos];
if(npos!=n) {
++sweep[0][npos];
--sweep[0][npos+1];
}
}
}
}
}
return ans;
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
n=sz(s);
k=sz(c);
//cout<<"n = "<<n<<" k = "<<k<<endl;
rep(i,0,2) sweep[i].assign(n+1,0);
memo.assign(n,vll(k+1,-1));
nxt_white.assign(n,0);
colors=s;
trav(num,c) blocks.pb(num);
ll npos=n;
per(i,0,n) {
if(colors[i]=='_') npos=i;
nxt_white[i]=npos;
}
assert(dp(0,0));
string ans="";
ll white=0,black=0;
rep(i,0,n) {
white+=sweep[0][i];
black+=sweep[1][i];
if(white&&black) ans+='?';
else if(white) ans+='_';
else if(black) ans+='X';
else assert(0);
}
return ans;
}
/*
#include <vector>
#include <string>
#include <cstdio>
#include <cassert>
const int S_MAX_LEN = 200 * 1000;
char buf[S_MAX_LEN + 1];
int main() {
assert(1 == scanf("%s", buf));
std::string s = buf;
int c_len;
assert(1 == scanf("%d", &c_len));
std::vector<int> c(c_len);
for (int i = 0; i < c_len; i++) {
assert(1 == scanf("%d", &c[i]));
}
std::string ans = solve_puzzle(s, c);
printf("%s\n", ans.data());
return 0;
}*/
