#include <bits/stdc++.h>
using namespace std;
const int dydis = 1e2 + 10;
int dp[dydis][dydis][dydis][2]; // jei esu i-ajame characteryje, j-ojoje grupeje, jau su manimi is viso yra h bloku, o as esu l characteris, tai ar galima taip padaryt?
string S;
vector<int> mas;
int hsh(char a){
if(a == '_') return 0;
if(a == 'X') return 1;
return 2;
}
int galiButi[dydis][2] = {0};
bool galima(int i1, int i2, int sitasBlokasJau, int asEsu){
// cout << "dp[" << i1 << "][" << i2 << "][" << sitasBlokasJau << "][" << asEsu << "] = ?\n";
if(i1 == S.size()){
if(i2 == mas.size() && sitasBlokasJau == 0) return true;
return false;
}
if(sitasBlokasJau == 1 && i2 == mas.size()) return false;
if(S[i1] != '.'){
if(hsh(S[i1]) != asEsu) return false;
}
if(dp[i1][i2][sitasBlokasJau][asEsu] != -1) return dp[i1][i2][sitasBlokasJau][asEsu];
// dabar kazka desiu i kita!
bool ret = 0;
if(asEsu == hsh('_')){ // jei as esu _, tai toliau galiu testi save, arba pradeti nauja etapa
bool p1 = 0, p2 = 0;
p1 = galima(i1+1, i2, 1, hsh('X'));
p2 = galima(i1+1, i2, 0, hsh('_'));
ret = p1 | p2;
}else{ // jei as esu X, tai privalau arba testi, arba privalau uzbaigti etapa
if(sitasBlokasJau == mas[i2]) { // privalau uzbaigti
ret = galima(i1+1, i2+1, 0, hsh('_'));
}else{ // privalau testi
ret = galima(i1+1, i2, sitasBlokasJau+1, hsh('X'));
}
}
if(ret){
galiButi[i1][asEsu] = 1;
}
// cout << "dp[" << i1 << "][" << i2 << "][" << sitasBlokasJau << "][" << asEsu << "] = " << ret << endl;
return dp[i1][i2][sitasBlokasJau][asEsu] = ret;
// esu jau nustates S[i1]
}
string solve_puzzle(string s, vector<int> c) {
for(int i = 0; i < dydis; i++){
for(int j = 0; j < dydis; j++){
for(int h = 0; h < dydis; h++){
for(int l = 0; l < 2; l++){
dp[i][j][h][l] = -1;
}
}
}
}
int k = c.size();
S = s;
mas = c;
galima(0, 0, 0, hsh('_'));
galima(0, 0, 1, hsh('X'));
string ret = "";
for(int i = 0; i < s.size(); i++){
if(galiButi[i][hsh('_')] == 1 && galiButi[i][hsh('X')]){
ret.push_back('?');
}else if(galiButi[i][hsh('X')] == 1){
ret.push_back('X');
}else if(galiButi[i][hsh('_')] == 1){
ret.push_back('_');
}else{
ret.push_back('!');
}
}
return ret;
}
