#include<bits/stdc++.h>
#include "paint.h"
#include <cstdlib>
using namespace std;
struct BIT{
int N;
vector<int> arr;
BIT(){}
BIT(int n){
N = n + 1;
arr = vector<int> (N);
}
void _u(int i, int val){
if(i < N) arr[i] += val;
}
void u(int a, int b){
a++;
b++;
_u(b+1,-1);
_u(a,1);
}
void start(){
for(int i = 1; i < N; i++) arr[i] += arr[i-1];
}
int q(int i){
i++;
return arr[i];
}
};
const int MN = 200000;
int N, K;
string S;
vector<int> C;
vector<vector<int>> dp (MN + 10, vector<int> (101, -1));
vector<int> pref (MN), pref2(MN);
BIT bitx, bitw;
int rec(int i1, int i2){
if(dp[i1][i2] != -1) return dp[i1][i2];
if(i2 == K){
dp[i1][i2] = 1;
if(i1 >= N) return 1;
int c = pref2[N-1] - (i1 == 0 ? 0 : pref2[i1-1]);
dp[i1][i2] = c == 0;
if(dp[i1][i2]){
bitw.u(i1,N-1);
}
return dp[i1][i2];
}
dp[i1][i2] = 0;
if(i1 + C[i2] - 1 >= N) return dp[i1][i2];
int c = pref[i1 + C[i2] - 1] - (i1 == 0 ? 0 : pref[i1-1]);
int t = i1 + C[i2];
if(c == 0 && (t == N || S[t] != 'X') && rec(i1 + C[i2] + 1, i2+1)){
if(t < N){
bitw.u(t,t);
}
bitx.u(i1,i1+C[i2]-1);
dp[i1][i2] = 1;
}
if(S[i1] != 'X' && rec(i1 + 1, i2)){
bitw.u(i1,i1);
dp[i1][i2] = 1;
}
//cout << i1 << " " << i2 << " " << dp[i1][i2] << endl;
return dp[i1][i2];
}
string solve_puzzle(string _s, vector<int> _c) {
//cout << "input: " << _s << endl;
S = _s;
C = _c;
//for(auto e : C) cout << e << " ";
//cout << endl;
N = S.length();
K = C.size();
pref[0] = (S[0] == '_');
for(int i = 1; i < N; i++){
pref[i] = pref[i-1] + (S[i] == '_');
}
pref2[0] = (S[0] == 'X');
for(int i = 1; i < N; i++){
pref2[i] = pref2[i-1] + (S[i] == 'X');
}
bitx = BIT(N);
bitw = BIT(N);
rec(0, 0);
string res (N, '?');
bitx.start();
bitw.start();
for(int i = 0; i < N; i++){
/*if(S[i] == 'X') x[i] = 1;
else if(S[i] == '_') w[i] = 1;
if(w[i] == 0 && x[i] == 0) w[i] = 1;*/
int tx = bitx.q(i);
int tw = bitw.q(i);
if(tx > 0 && tw == 0) res[i] = 'X';
else if(tx == 0 && tw > 0) res[i] = '_';
}
return res;
}
