#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 100;
const int maxl = 1e1 + 100;
int n, k;
bool dp[maxn][maxl];
bool d[maxn][maxl];
int a[maxn];
int b[maxn];
int c[maxn];
string s;
int w[maxn];
int bl[maxn];
bool ok(int l, int r, int c){
if(r > n || l < 1) return 0;
if(c){
if(b[r] > b[l-1]) return 0;
return 1;
} else{
if(a[r] > a[l-1]) return 0;
return 1;
}
}
string solve_puzzle(std::string S, std::vector<int> C){
s = S;
n = s.size();
s = "#" + s; k = C.size();
for(int i = 1; i <= k; i++){
c[i] = C[i-1];
}
for(int i = 1; i <= n; i++){
a[i] = a[i-1]; b[i] = b[i-1];
if(s[i] == 'X') a[i]++;
if(s[i] == '_') b[i]++;
}
dp[0][0] = 1;
for(int i = 1; i <= n; i++){
for(int j = 0; j <= k; j++){
if(ok(i, i, 0) && dp[i-1][j]){
dp[i][j] = 1;
}
if(j){
int l = i - c[j] - 1;
if(j == 1) l++;
if(l >= 0 && dp[l][j-1] && ok(i - c[j] + 1, i, 1) && (j == 1 || ok(l+1, l+1, 0))){
dp[i][j] = 1;
}
}
}
}
d[n+1][k+1] = 1;
for(int i = n; i > 0; i--){
for(int j = k + 1; j > 0; j--){
if(ok(i, i, 0) && d[i+1][j]){
d[i][j] = 1;
}
if(j <= k){
int r = i + c[j] + 1;
if(j == k) r--;
if(r <= n + 1 && d[r][j+1] && ok(i, i + c[j] - 1, 1) && (j == k || ok(r-1, r-1, 0))){
d[i][j] = 1;
}
}
}
}
for(int i = 1; i <= n; i++){
if(ok(i, i, 0)){
for(int j = 0; j <= k; j++){
if(dp[i-1][j] && d[i+1][j+1]){
w[i] = 1;
}
}
}
for(int j = 1; j <= k; j++){
if(ok(i, i + c[j] - 1, 1)){
int l = i - 2;
int r = i + c[j] + 1;
if(j == 1) l++;
else if(!ok(i-1, i-1, 0)) continue;
if(j == k) r--;
else if(!ok(i+c[j], i+c[j], 0)) continue;
if(dp[l][j-1] && d[r][j+1]){
bl[i]++; bl[i + c[j]]--;
}
}
}
}
string res;
vector<int> ans = {'.', '_', 'X', '?'};
for(int i = 1; i <= n; i++){
bl[i] += bl[i-1];
int x = w[i];
if(bl[i]) x |= 2;
res.push_back(ans[x]);
}
return res;
}
