#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) {
// cout << st << " " << ki << " " << flag << endl;
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;
for(int i = st + 1; i <= n; i++) {
int cur = rec(i, ki, 0);
if(cur) {
dp2[i][ki][0]++;
}
answ |= cur;
if(curr[i] == '_') {
lst = i;
continue;
}
if(!flag && i - lst >= C[ki + 1]) {
int curr = rec(i, ki + 1, 1);
if(curr) {
int j = i, cnt = 0;
while(cnt < C[ki + 1]) {
dp2[j][ki + 1][1]++;
j--, cnt++;
}
}
answ |= curr;
}
if(flag && i - lst > C[ki + 1]) {
int curr = rec(i, ki + 1, 1);
if(curr) {
int j = i, cnt = 0;
while(cnt < C[ki + 1]) {
dp2[j][ki + 1][1]++;
j--, cnt++;
}
}
answ |= curr;
}
}
} else {
for(int i = st + 1; i <= n; i++) {
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];
}
// cout << curr << endl;
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++;
}
if(dp2[i][j][1]) {
cnt2++;
}
if(cnt1 && cnt2) {
break;
}
}
// if(i == 4) {
// cout << cnt1 << " " << cnt2 << endl;
// }
if(cnt1 && !cnt2) {
answ += "_";
} else if(!cnt1 && cnt2) {
answ += "X";
} else {
answ += "?";
}
}
return answ;
}
