#include <bits/stdc++.h>
#include "paint.h";
using namespace std;
int n,k,t,lst1,lst2,sum,arr[101],pref[200001],nxt_[200001],nxtX[200001],pre_[200001],preX[200001];
vector<int> segment[102][2];
string s;
int getval(int tag , int tag2 , int a , int b , int curr , int l , int r){
if(b < l || a > r || b < a){
return 0;
}
if(a <= l && b >= r){
return segment[tag2][tag][curr];
}
int mid = (l+r)/2;
return max(getval(tag,tag2,a,b,2*curr,l,mid),getval(tag,tag2,a,b,2*curr+1,mid+1,r));
}
void upd(int tag , int tag2 , int pos , int val){
while(pos){
segment[tag2][tag][pos] = max(segment[tag2][tag][pos],val);
pos /= 2;
}
}
string solve_puzzle(string s , vector<int> c){
s = "###"+s+"##";
k = c.size();
n = s.size()-3;
t = pow(2,ceil(log2(n+4)));
for(int i = 0 ; i <= k+1 ; i += 1){
segment[i][0].resize(2*t,0);
segment[i][1].resize(2*t,0);
}
for(int i = 1 ; i <= n ; i += 1){
if(s[i] == 'X'){
break;
}
upd(0,0,i+t-1,1);
}
for(int i = n+2 ; i >= 1 ; i -= 1){
if(s[i] == 'X'){
break;
}
upd(1,k+1,i+t-1,1);
}
for(int i = 1 ; i <= k ; i += 1){
arr[i] = c[i-1];
}
lst1 = n+2 , lst2 = n+1;
for(int i = n+2 ; i >= 0 ; i -= 1){
if(s[i] == 'X'){
lst1 = i;
}else if(s[i] == '_'){
lst2 = i;
}
nxt_[i] = lst2 , nxtX[i] = lst1;
}
lst1 = 1 , lst2 = 2;
for(int i = 0 ; i <= n+2 ; i += 1){
if(s[i] == 'X'){
lst1 = i;
}else if(s[i] == '_'){
lst2 = i;
}
pre_[i] = lst2 , preX[i] = lst1;
}
for(int i = n ; i >= 3 ; i -= 1){
for(int j = k ; j >= 1 ; j -= 1){
if(nxt_[i] < i+arr[j]){
continue;
}
upd(1,j,i+t-1,getval(1,j+1,i+arr[j]+1,nxtX[i+arr[j]],1,1,t));
}
}
for(int i = 3 ; i <= n ; i += 1){
for(int j = 1 ; j <= k ; j += 1){
if(pre_[i] > i-arr[j]){
continue;
}
upd(0,j,i+t-1,getval(0,j-1,preX[i-arr[j]],i-arr[j]-1,1,1,t));
}
}
string ans = "";
for(int i = 3 ; i <= n ; i += 1){
bool b = 0 , w = 0;
for(int j = 1 ; j <= k+1 ; j += 1){
if(s[i] != 'X' && getval(1,j,i+1,nxtX[i],1,1,t) && getval(0,j-1,preX[i],i-1,1,1,t)){
w = 1;
}
if(j <= k && segment[j][1][i+t-1] && getval(0,j-1,preX[i-1],i-2,1,1,t)){
pref[i] += 1 , pref[i+arr[j]] -= 1;
}
}
sum += pref[i];
b = (sum > 0 ? 1 : 0);
if(b && w){
ans += '?';
}else if(b){
ans += 'X';
}else{
ans += '_';
}
}
return ans;
}
