#include <bits/stdc++.h>
using namespace std;
const int dydis1 = 1e5 + 10;
const int dydis2 = 1e2 + 10;
short dp[dydis1][dydis2]; // 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[dydis1][2] = {0};
int kiek_(int l, int r){
int ret = 0;
for(int i = l; i <= r; i++){
ret += S[i] == '_';
}
return ret;
}
void nustatyk(int l, int r, int kas){
for(int i = l; i <= r; i++){
galiButi[i][kas] = 1;
}
}
bool galima(int i1, int i2){ // as esu i1, dabartine grupe bus pildoma i2, ir pries mane yra padetas _
if(mas[i1] == 'X') return false;
if(i1 >= S.size()){
return i2 == mas.size();
}
if(dp[i1][i2] != -1) return dp[i1][i2];
// desiu X
int ret = 0;
if(i2 < mas.size() && i1 + mas[i2]-1 < S.size()){ // jei galiu deti X-u eile ir jei X-ai isvis telpa
int kek = kiek_ (i1, i1+mas[i2]-1);
if(kek == 0 && (i1 + mas[i2] == S.size() || S[i1+mas[i2]] != 'X')){ // jei nera trukdziu nei tarpe nei sone
int p1 = galima(i1 + mas[i2]+1, i2+1);
if(p1){
ret = 1;
nustatyk(i1, i1+mas[i2]-1, hsh('X')); // nustatyk ,kad gali X-a paimti
nustatyk(i1+mas[i2], i1 + mas[i2], hsh('_'));
}
}
}
if(S[i1] != 'X'){
if(galima(i1+1, i2)){
ret = 1;
nustatyk(i1, i1, hsh('_'));
}
}
// cout << "DP[" << i1 << "][" << i2 << "] = " << ret << endl;
return dp[i1][i2] = ret;
// desiu _
}
string solve_puzzle(string s, vector<int> c) {
for(int i = 0; i < dydis1; i++){
for(int j = 0; j < dydis2; j++){
dp[i][j] = -1;
}
}
int k = c.size();
S = s;
mas = c;
if(c[0] == 'X'){
nustatyk(0, mas[0]-1, hsh('X'));
nustatyk(mas[0], mas[0], hsh('_'));
galima(mas[0]+1, 1);
}else{
galima(0, 0);
}
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;
}
