#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
const int N=2e5+5,K=1e2+5;
int n,k;
bool dpL[N][K],dpR[N][K];
bool canW[N],canB[N];
int white[N],black[N];
string s;
vector<int>c;
int getW(int l,int r){
return white[r]-white[l-1];
}
int getB(int l,int r){
return black[r]-black[l-1];
}
string solve_puzzle(string S,vector<int>C){
n=S.size(),k=C.size();
s=" ";
s+=S;
c.pb(0);
c.insert(c.end(),all(C));
white[0]=black[0]=0;
for(int i=1;i<=n;i++){
white[i]=white[i-1]+(s[i]=='_'?1:0);
black[i]=black[i-1]+(s[i]=='X'?1:0);
}
dpL[0][0]=true;
for(int i=1;i<=n;i++){
if(getB(1,i)==0){
dpL[i][0]=true;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
if(s[i]=='W'){
dpL[i][j]=dpL[i-1][j];
}
else if(s[i]=='B'){
// i-c[j]+1 , i black
// i-c[j] white
if(1<=i-c[j]+1&&getW(i-c[j]+1,i)==0){
if(i-c[j]==0){
if(j==1) dpL[i][j]=true;
}
else if(s[i-c[j]]!='X'){
dpL[i][j]=dpL[i-c[j]-1][j-1];
}
}
}
else{
bool ok=false;
if(dpL[i-1][j]==true) ok|=true;
if(1<=i-c[j]+1&&getW(i-c[j]+1,i)==0){
if(i-c[j]==0){
if(j==1) ok|=true;
}
else if(s[i-c[j]]!='X'){
ok|=dpL[i-c[j]-1][j-1];
}
}
dpL[i][j]=ok;
}
}
}
dpR[n+1][k+1]=true;
for(int i=n;i>=1;i--){
if(getB(i,n)==0){
dpR[i][k+1]=true;
}
}
for(int i=n;i>=1;i--){
for(int j=k;j>=1;j--){
if(s[i]=='W'){
dpR[i][j]=dpR[i+1][j];
}
else if(s[i]=='B'){
// i , i+c[j]-1 black
// i+c[j] white
if(i+c[j]-1<=n&&getW(i,i+c[j]-1)==0){
if(i+c[j]==n+1){
if(j==k) dpR[i][j]=true;
}
else if(s[i+c[j]]!='X'){
dpR[i][j]=dpR[i+c[j]+1][j+1];
}
}
}
else{
bool ok=false;
if(dpR[i+1][j]==true) ok|=true;
if(i+c[j]-1<=n&&getW(i,i+c[j]-1)==0){
if(i+c[j]==n+1){
if(j==k) ok|=true;
}
else if(s[i+c[j]]!='X'){
ok|=dpR[i+c[j]+1][j+1];
}
}
dpR[i][j]=ok;
}
}
}
for(int i=1;i<=n;i++){
canW[i]=false;
for(int j=0;j<=k;j++){
if(dpL[i-1][j]==true&&dpR[i+1][j+1]==true){
canW[i]=true;
}
}
}
vector<int>add(N),sub(N);
int cur=0;
for(int j=1;j<=k;j++){
for(int l=1,r=c[j];r<=n;l++,r++){
bool ok=true;
if(getW(l,r)!=0) continue;
if(l-1>=1&&s[l-1]=='B') continue;
if(r+1<=n&&s[r+1]=='B') continue;
if(l==1&&j>1) continue;
if(l>1&&dpL[l-2][j-1]==false) continue;
if(r==n&&j<k) continue;
if(r<n&&dpR[r+2][j+1]==false) continue;
add[l]++;
sub[r]++;
}
}
for(int i=1;i<=n;i++){
canB[i]=false;
cur+=add[i];
if(cur>0) canB[i]=true;
cur-=sub[i];
}
string ans(n,'.');
for(int i=1;i<=n;i++){
if(canW[i]&&canB[i]) ans[i-1]='?';
else if(canW[i]) ans[i-1]='_';
else if(canB[i]) ans[i-1]='X';
}
return ans;
}
