#include "paint.h"
#include "bits/stdc++.h"
#define MAXN 200009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x) cerr<< #x <<" = "<< x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int n,k;
int arr[MAXN],par[MAXN],white[MAXN],black[MAXN],arap[MAXN];
string s;
const int K=103;
bool pre[K][MAXN],suf[K][MAXN];
string solve_puzzle(string tmp,vector<int> c) {
s="#"+tmp+"#";n=int(tmp.size());k=int(c.size());
for(int i=1;i<=k;i++)arr[i]=c[i-1];
for(int i=1;i<=n;i++)par[i]=par[i-1]+(s[i]=='_');//count white
for(int i=1;i<=n+1;i++)arap[i]=arap[i-1]+(s[i]=='X');//count black
if(k==1){
for(int i=1;i+arr[1]<=n+1;i++)
if(par[arr[1]+i-1]==par[i-1] and !arap[i-1] and arap[n+1]==arap[i+arr[1]-1]){
for(int h=i;h<arr[1]+i;h++)
black[h]=1;
for(int h=1;h<i;h++)
white[h]=1;
for(int h=arr[1]+i;h<=n;h++)
white[h]=1;
}
}
else{
pre[0][0]=1;
for(int i=0;i<=k;i++){
for(int j=1;j<=n;j++){
if(s[j]!='X')
pre[i][j]=pre[i][j-1];
else
pre[i][j]=0;
if(i and j>=arr[i] and par[j]==par[j-arr[i]] and s[j-arr[i]]!='X'){
if(i==1)
pre[i][j]|=pre[i-1][j-arr[i]];
else if(j>arr[i])
pre[i][j]|=pre[i-1][j-arr[i]-1];
}
}
}
suf[k+1][n+1]=1;
for(int i=k+1;i>=1;i--){
for(int j=n;j>=1;j--){
if(s[j]!='X')
suf[i][j]=suf[i][j+1];
else
suf[i][j]=0;
if(i<=k and j+arr[i]<=n+1 and par[j-1]==par[j+arr[i]-1] and s[j+arr[i]]!='X'){
if(i==k)
suf[i][j]|=suf[i+1][j+arr[i]];
else if(j+arr[i]<=n)
suf[i][j]|=suf[i+1][j+arr[i]+1];
}
}
}
/*
for(int i=0;i<=k;i++){
for(int j=0;j<=n;j++)
printf("dp[%d][%d] = %d\n",i,j,suf[i][j]);
wr
}
*/
for(int i=1;i<=n;i++)
if(s[i]=='.'){
white[i]=0;
for(int j=0;j<=k;j++)
white[i]|=(pre[j][i-1] and suf[j+1][i+1]);
}
for(int i=1;i<=k;i++)
for(int j=1;j+arr[i]<=n+1;j++){
if(i==1){
if(j+arr[i]<=n and par[j+arr[i]-1]==par[j-1] and pre[i-1][j-1] and suf[i+1][j+arr[i]+1] and s[j+arr[i]]!='X'){
for(int h=j;h<j+arr[i];h++){
black[h]=1;
}
}
}
else if(i==k){
if(j>=2 and par[j+arr[i]-1]==par[j-1] and pre[i-1][j-2] and suf[i+1][j+arr[i]] and s[j-1]!='X'){
for(int h=j;h<j+arr[i];h++){
black[h]=1;
}
}
}
else{
if(j>=2 and j+arr[i]<=n and par[j+arr[i]-1]==par[j-1] and pre[i-1][j-2] and suf[i+1][j+arr[i]+1]
and s[j+arr[i]]!='X' and s[j-1]!='X'){
for(int h=j;h<j+arr[i];h++){
black[h]=1;
}
}
}
}
}
for(int i=0;i<n;i++)
if(tmp[i]=='.'){
if(black[i+1] and white[i+1])
tmp[i]='?';
else if(black[i+1])
tmp[i]='X';
else
tmp[i]='_';
}
return tmp;
}
