#include "paint.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,int>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
int arr[105];
int white[200005];
int black[200005];
int n,k;
int f(int a, int b){
//can i tile black
int hold=white[b]-white[a-1];
if(hold>=1) return 0;
else return 1;
}
int f2(int a, int b){
//can i tile white
int hold=black[b]-black[a-1];
if(hold>=1) return 0;
else return 1;
}
int memo[200005][105];
bool dp(int index, int cur){
if(index>n){
if(cur==k) return 1;
else return 0;
}
if(memo[index][cur]!=-1) return memo[index][cur];
bool ans=false;
//white
if(f2(index,index)){
ans|=dp(index+1,cur);
}
//black
if(cur<k&&index+arr[cur]<=n&&f(index,index+arr[cur]-1)&&f2(index+arr[cur],index+arr[cur])){
ans|=dp(index+arr[cur]+1,cur+1);
}
return memo[index][cur]=ans;
}
bool visited[200005][105];
int black2[200005];
int white2[200005];
void dfs(int index, int cur){
if(index>n) return;
if(visited[index][cur]) return;
visited[index][cur]=true;
if(f2(index,index)&&memo[index+1][cur]==1){
dfs(index+1,cur);
white2[index]++;
white2[index+1]--;
}
if(cur<k&&index+arr[cur]<=n&&f(index,index+arr[cur]-1)&&f2(index+arr[cur],index+arr[cur])&&memo[index+arr[cur]+1][cur+1]){
//cout << index << " " << cur << " black\n";
dfs(index+arr[cur]+1,cur+1);
black2[index]++;
black2[index+arr[cur]]--;
white2[index+arr[cur]]++;
white2[index+arr[cur]+1]--;
}
}
string solve_puzzle(string s, vector<int> c) {
k=c.size();
for(int x=0;x<k;x++){
arr[x]=c[x];
}
s=" "+s;
n=s.length();
for(int x=1;x<n;x++){
white[x]=white[x-1];
black[x]=black[x-1];
if(s[x]=='X') black[x]++;
else if(s[x]=='_') white[x]++;
//cout << black[x] << " " << white[x] << "\n";
}
memset(memo,-1,sizeof(memo));
dp(1,0);
//backtrack
dfs(1,0);
string ans="";
for(int x=1;x<n;x++){
white2[x]+=white2[x-1];
black2[x]+=black2[x-1];
if(white2[x]>0&&black2[x]>0) ans+='?';
else if(white2[x]>0) ans+='_';
else ans+='X';
}
return ans;
}
