#include <bits/stdc++.h>
using namespace std;
struct ST{
int N;
vector<int> tree;
ST(int n){
N = (1LL<<(int)ceil(log2(n)));
tree = vector<int>(2*N);
}
void update(int k, int val){
k += N;
tree[k] += val;
for(k /= 2; k >= 1; k /= 2)
tree[k] = tree[2*k]+tree[2*k+1];
}
int query(int a, int b){
a += N, b += N;
int ans = 0;
while(a <= b){
if(a%2 == 1) ans += tree[a++];
if(b%2 == 0) ans += tree[b--];
a /= 2, b /= 2;
}
return ans;
}
};
string solve_puzzle(string s, vector<int> c){
if(s.size() == 1) return "X"; //Caso bomba :)
int n = s.size(), k = c.size();
c.insert(c.begin(), 0); //Pasar c a 1-index
c.push_back(0);
vector<int> pw(n+1), pb(n+1);
for(int i=0; i<n; i++){
pw[i+1] = pw[i]+(s[i] == '_' ? 1 : 0);
pb[i+1] = pb[i]+(s[i] == 'X' ? 1 : 0);
}
//
auto wh = [&](int l, int r){
return pw[r+1]-pw[l];
};
auto bl = [&](int l, int r){
return pb[r+1]-pb[l];
};
//
vector<vector<int>> l(n, vector<int>(k+2)), r(n, vector<int>(k+2));
for(int i=0; i<n; i++){
if(bl(0, i) == 0) l[i][0] = 1;
if(bl(i, n-1) == 0) r[i][k+1] = 1;
}
for(int j=1; j<=k; j++)
for(int i=0; i<n; i++){
if(i-1 >= 0 && s[i] != 'X') l[i][j] |= l[i-1][j];
if(i+c[j]-1 < n && ((i-2 < 0 && j == 1) || (i-2 >= 0 && l[i-2][j-1])) &&
wh(i, i+c[j]-1) == 0 && (i-1 < 0 || s[i-1] != 'X') && (i+c[j] >= n || s[i+c[j]] != 'X')){
//cerr << i+c[j]-1 << " " << j << "\n";
l[i+c[j]-1][j] = 1;
}
}
for(int j=k; j>=1; j--)
for(int i=n-1; i>=0; i--){
if(i+1 < n && s[i] != 'X') r[i][j] |= r[i+1][j];
if(i-c[j]+1 >= 0 && ((i+2 >= n && j == k) || (i+2 < n && r[i+2][j+1])) &&
wh(i-c[j]+1, i) == 0 && (i+1 >= n || s[i+1] != 'X') && (i-c[j] < 0 || s[i-c[j]] != 'X')){
//cerr << i-c[j]+1 << " " << j << "\n";
r[i-c[j]+1][j] = 1;
}
}
string ans = string(n, '?');
for(int i=0; i<n; i++){
bool ok = 0;
if(i == 0) ok = r[i+1][1];
else if(i == n-1) ok = l[i-1][k];
else {
for(int j=0; j<=k && !ok; j++)
ok |= (l[i-1][j] && r[i+1][j+1]);
}
if(!ok || s[i] == 'X') ans[i] = 'X';
}
ST st(n+1);
for(int j=1; j<=k; j++)
for(int i=0; i<n; i++){
if(i+c[j]-1 < n && ((i-2 < 0 && j == 1) || (i-2 >= 0 && l[i-2][j-1])) && ((i+c[j]+1 >= n && j == k) || (i+c[j]+1 < n && r[i+c[j]+1][j+1])) &&
(i-1 < 0 || s[i-1] != 'X') && (i+c[j] >= n || s[i+c[j]] != 'X') && wh(i, i+c[j]-1) == 0){
st.update(i, 1); st.update(i+c[j], -1);
}
}
for(int i=0; i<n; i++)
if(st.query(0, i) == 0 || s[i] == '_') ans[i] = '_';
return ans;
}
