#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
int black[200005];
int white[200005];
int pre[104][200005];
int suf[105][200005];
int sum[2][200005];
int val[200006];
int psum[200005];
int ssum[200005];
int l[200005];
int cpre[105][200005];
int csuf[105][200005];
string solve_puzzle(string s, vector<int> c) {
int k=c.size();
int n=s.size();
for(int i=1;i<=n;i++){
sum[1][i]=sum[1][i-1];
sum[2][i]=sum[2][i-1];
if(s[i-1]=='.')val[i]=1;
else if(s[i-1]=='_')val[i]=2,sum[2][i]++;
else val[i]=3,sum[1][i]++;
}
for(int i=0;i<=k+1;i++)pre[i][0]=suf[i][n+1]=1;
for(int i=0;i<=n+1;i++)cpre[0][i]=1,csuf[k+1][i]=n;
for(int i=1;i<=k;i++)l[i]=c[i-1],psum[i]=psum[i-1]+l[i]+1;
for(int i=k;i>=1;i--)ssum[i]=ssum[i+1]+l[i]+1;
for(int i=1;i<=k;i++){
for(int j=1;j<=n;j++){
if((i==1&&j>=l[i])||(j-l[i]-1>=0)){
if(sum[2][j]-sum[2][j-c[i-1]]==0&&(i==1||cpre[i-1][j-l[i]-1])){
if(i==1&&sum[1][j-l[i]]!=0)continue;
if(i!=1&&sum[1][j-l[i]]-sum[1][cpre[i-1][j-l[i]-1]]!=0)continue;
pre[i][j]=1;
}
}
}
for(int j=1;j<=n;j++){
cpre[i][j]=cpre[i][j-1];
if(pre[i][j])cpre[i][j]=j;
}
}
for(int i=k;i>=1;i--){
for(int j=n;j>=1;j--){
if((i==k&&j+l[i]-1<=n)||(j+l[i]+1<=n)){
if(sum[2][j+l[i]-1]-sum[2][j-1]==0&&(i==k||csuf[i+1][j+l[i]+1])){
if(i==k&&sum[1][n]-sum[1][j+l[i]-1]!=0)continue;
if(i!=k&&sum[1][csuf[i+1][j+l[i]+1]-1]-sum[1][j+l[i]-1]!=0)continue;
suf[i][j]=1;
}
}
}
for(int j=n;j>=1;j--){
csuf[i][j]=csuf[i][j+1];
if(suf[i][j])csuf[i][j]=j;
}
}
for(int i=1;i<=k;i++){
for(int j=1;j+l[i]-1<=n;j++){
if(pre[i][j+l[i]-1]&&suf[i][j]){
black[j]++;
black[j+l[i]]--;
}
}
}
for(int i=0;i<=k;i++){
for(int j=1;j<=n;j++){
if(cpre[i][j-1]&&csuf[i+1][j+1]){
if(sum[1][csuf[i+1][j+1]-1]-sum[1][cpre[i][j-1]]!=0)continue;
white[j]++;
white[j+1]--;
}
}
}
/*cerr<<"PRE:\n";
for(int i=1;i<=k;i++){
for(int j=1;j<=n;j++){
cerr<<pre[i][j]<<" ";
}
cerr<<"\n";
}
cerr<<"\n";
cerr<<"SUF:\n";
for(int i=1;i<=k;i++){
for(int j=1;j<=n;j++){
cerr<<suf[i][j]<<" ";
}
cerr<<"\n";
}
cerr<<"\n";*/
string ans(n,'?');
for(int i=1;i<=n;i++){
black[i]+=black[i-1];
white[i]+=white[i-1];
if(black[i]&&white[i]){
ans[i-1]='?';
}else if(black[i]){
ans[i-1]='X';
}else{
ans[i-1]='_';
}
}
return ans;
}
