#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
string solve_single(int n,int c){
int w[n],b[n];
memset(w,0,sizeof(w));
memset(b,0,sizeof(b));
for(int i=0;i<n;i++)b[i]=w[i]=1;
int r =c-1;
int l = n-c;
for(int i=l;i<=r;i++)w[i]=0;
string ans = "";
for(int i=0;i<n;i++)
if(w[i]+b[i]==2)ans+="?";
else if(w[i]+b[i]==1)ans += (w[i]==1?"_":"X");
else ans += "_";
//cout << n << "\t" << c << "\t" << ans << "\n";
return ans;
}
string solve_puzzle(string s,vector<int> c){
int n=s.length(),m=c.size();
vector<int> left;
int p =0;
for(int x:c){
left.push_back(p);
p+=x+1;
}
vector<int> right;
p = n-1;
for(int i=m-1;i>=0;i--){
right.push_back(p);
p -= c[i]+1;
}
reverse(right.begin(),right.end());
string ans = "";
int w[n],b[n];
memset(w,0,sizeof(w));
memset(b,0,sizeof(b));
for(int i=0;i<m;i++){
string r = solve_single(right[i]-left[i]+1,c[i]);
p = 0;
for(int j=left[i];j<=right[i];j++){
char C = r[p++];
if(C=='_')w[j]=1;
else if(C=='X')b[j]=1;
else w[j]=b[j]=1;
}
}
for(int i=0;i<n;i++)
if(w[i]+b[i]==2)ans+="?";
else if(w[i]+b[i]==1)ans += (w[i]==1?"_":"X");
else ans += "_";
return ans;
}
