#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
#define ll long long
#define ld long double
#define all(x) (x.begin(), x.end())
#define rall(x) (x.rbegin(), x.rend())
#define sz(x) (int)x.size()
const int N = 2e5 + 10, K = 1e2 + 10;
int dp[N][K][2], C[N], n, k;
int dp2[N][K][2];
string curr;
// 1 is if true
// -1 is if undef
// 0 if false
int rec(int st, int ki, int flag) {
if(st == n && ki == k) {
return 1;
} else if(st == n) {
dp[st][ki][flag] = 0;
return 0;
}
if(dp[st][ki][flag] != -1) {
return dp[st][ki][flag];
}
int answ = 0;
if(ki != k) {
int lst = st, lstX = -1;
for(int i = st + 1; i <= n; i++) {
if(curr[i] != 'X' && lstX == -1) {
int cur = rec(i, ki, 0);
if(cur) {
dp2[i][ki][0]++;
}
answ |= cur;
}
if(curr[i] == '_') {
lst = i;
continue;
}
if(curr[i] != '_') {
if(!flag && i - lst >= C[ki + 1] && (lstX == -1 || lstX > (i - C[ki + 1]))) {
int curr = rec(i, ki + 1, 1);
if(curr) {
int prefStart = i - C[ki + 1] + 1, prefEnd = i + 1;
dp2[prefStart][ki + 1][1]++;
dp2[prefEnd][ki + 1][1]--;
}
answ |= curr;
}
if(flag && i - lst > C[ki + 1] && (lstX == -1 || lstX > (i - C[ki + 1]))) {
int curr = rec(i, ki + 1, 1);
if(curr) {
int prefStart = i - C[ki + 1] + 1, prefEnd = i + 1;
dp2[prefStart][ki + 1][1]++;
dp2[prefEnd][ki + 1][1]--;
}
answ |= curr;
}
if(curr[i] == 'X' && lstX == -1) {
lstX = i;
}
}
}
} else {
for(int i = st + 1; i <= n; i++) {
if(curr[i] == 'X') {
dp[st][ki][flag] = 0;
return dp[st][ki][flag];
}
int cur = rec(i, ki, 0);
if(cur) {
dp2[i][ki][0]++;
}
answ |= cur;
}
}
dp[st][ki][flag] = answ;
return dp[st][ki][flag];
}
string solve_puzzle(string s, vector<int> c) {
memset(dp, -1, sizeof(dp));
n = sz(s);
curr += ".";
for(int i = 0; i < n; i++) {
curr += s[i];
}
k = sz(c);
for(int i = 0; i < k; i++) {
C[i + 1] = c[i];
}
rec(0, 0, 0);
string answ = "";
for(int i = 1; i <= n; i++) {
int cnt1 = 0, cnt2 = 0;
for(int j = 0; j <= k; j++) {
if(dp2[i][j][0]) {
cnt1++;
}
dp2[i][j][1] += dp2[i - 1][j][1];
if(dp2[i][j][1]) {
cnt2++;
}
if(cnt1 && cnt2) {
break;
}
}
if(cnt1 && !cnt2) {
answ += "_";
} else if(!cnt1 && cnt2) {
answ += "X";
} else {
answ += "?";
}
}
return answ;
}
