#include <bits/stdc++.h>
#include "paint.h"
//#include "grader.cpp"
using namespace std;
typedef long long ll;
const int MX=2e5+9;
int Pref[MX],dp[MX][102],c[102],n,k,White[MX],BL[MX];
string s,ans;
int GetSum(int l,int r){
int Pl=0;
if(l)Pl=Pref[l-1];
return Pref[r]-Pl;
}
void add(int l,int r){
BL[l]++;BL[r+1]--;
}
int DP(int x,int y){
if(x>=n){
if(y != k)return 0;
return 1;
}
int &ret=dp[x][y];if(ret!=-1)return ret;
ret=0;
if(y == k){
if(s[x] == 'X')return ret=0;
ret=DP(x+1,y);
if(ret)White[x] = 1;
return ret;
}
if(x + c[y] - 1 >= n)return ret=0;
bool OkWhite = 0, OkBlack = 0;
if(s[x] == '_'){
White[x] = 1;
return ret=DP(x+1,y);
}
else if(s[x] == 'X'){
add(x,x);
if(GetSum(x,x+c[y]-1) == 0 && s[x+c[y]] != 'X')ret = DP(x+c[y]+1,y+1);
if(ret){
add(x,x+c[y]-1);
White[x+c[y]] = 1;
}
return ret;
}
else{
OkWhite = DP(x+1,y);
if(GetSum(x,x+c[y]-1) == 0 && s[x+c[y]] != 'X'){
OkBlack = DP(x+c[y]+1,y+1);
if(OkBlack){
add(x,x+c[y]-1);
White[x+c[y]] = 1;
}
}
}
if(OkBlack && OkWhite) White[x] = 1, add(x,x);
else if(OkBlack) add(x,x);
else if(OkWhite) White[x] = 1;
return ret=max(OkWhite, OkBlack);
}
string solve_puzzle(string S, vector<int> C){
s=S;n=s.size();k=C.size();ans=s;s+="####";
for(int i=0;i<n;i++)White[i] = 0;
for(int i=0;i<k;i++)c[i]=C[i];
for(int i=0;i<n;i++)if(ans[i] == '.')ans[i] = '?';
Pref[0]=(s[0] == '_');
for(int i=1;i<n;i++)Pref[i]=Pref[i-1] + (s[i] == '_');
memset(dp,-1,sizeof(dp));
DP(0,0);
for(int i=0;i<n;i++){
if(i)BL[i] += BL[i-1];
if(BL[i] && White[i])ans[i] = '?';
else if(BL[i]) ans[i] = 'X';
else ans[i]='_';
}
return ans;
}
