#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<cstring>
#include<vector>
#include "paint.h"
using namespace std;
#define for1(i,n) for(int i=1;i<=(int)n;i++)
#define for0(i,n) for(int i=0;i<=(int)n;i++)
#define forn(i,n) for(int i=n;i>=1;i--)
#define fo(i,x,y) for(int i=x;i<=(int)y;i++)
#define fr(i,x,y) for(int i=x;i>=(int)y;i--)
#define pb push_back
#define mp make_pair
#define LL long long
const LL Mod=1000*1000*1000+7;
int n,k;
int dp[200002][102];
int ap[200002][102];
int minqan[200002];
int minaj[200002];
int mindzax[200002];
int C[1002];
string S;
int xdir1(int i,int j)
{
if((i-C[j]+1)>minaj[i] && S[i-C[j]]!='X')
return dp[max(0,i-C[j]-1)][j-1];
else
return 0;
}
int xdir2(int i,int j)
{
if((i-C[j]+1)>minaj[i] && S[i-C[j]]!='X')
return ap[max(0,i-C[j]-1)][j-1];
else
return 0;
}
void CALC()
{
for1(i,n)
{
if(S[i-1]=='_')
minaj[i]=i-1;
else
minaj[i]=minaj[i-1];
}
}
void calc1()
{
CALC();
dp[0][0]=1;
for1(i,n)
for0(j,k)
{
if(S[i]=='_')
dp[i][j]=dp[i-1][j];
else
{
if(S[i]=='X')
dp[i][j]=xdir1(i,j);
if(S[i]=='.')
{
dp[i][j]=max(dp[i-1][j],xdir1(i,j));
}
}
}
return;
}
void calc2()
{
CALC();
ap[0][0]=1;
for1(i,n)
for0(j,k)
{
if(S[i]=='_')
ap[i][j]=ap[i-1][j];
else
{
if(S[i]=='X')
{
ap[i][j]=xdir2(i,j);
}
if(S[i]=='.')
{
ap[i][j]=max(ap[i-1][j],xdir2(i,j));
}
}
}
return;
}
int minusik[200002];
int plusik[200002];
int add[200002];
void push(int v)
{
add[2*v]+=add[v];
add[2*v+1]+=add[v];
add[v]=0;
return ;
}
void update(int left,int right,int l,int r,int v,int val)
{
if(l>r)
return;
if(left==l && right==r)
{
add[v]+=val;
return ;
}
else
{
int m=(left+right)/2;
push(v);
update(left,m,l,min(r,m),2*v,val);
update(m+1,right,max(l,m+1),r,2*v+1,val);
}
}
int get(int left,int right,int pos,int v)
{
if(left==right)
{
if(add[v]>0)
return 1;
return 0;
}
else
{
int m=(left+right)/2;
push(v);
if(pos<=m)
return get(left,m,pos,2*v);
else
return get(m+1,right,pos,2*v+1);
}
}
string solve_puzzle(string s, vector<int> c)
{
k=c.size();
n=s.size();
for0(i,k-1)
C[i+1]=c[i];
S+='_';
S+=s;
calc1();
S.clear();
string t=s;
reverse(s.begin(),s.end());
S+='_';
S+=s;
for0(i,k-1)
C[i+1]=c[k-1-i];
calc2();
S.clear();
S+='_';
S+=t;
for0(i,k-1)
C[i+1]=c[i];
for1(i,n)
{
if(S[i]=='.')
{
int u=0;
for0(j,k)
{
u=max(u,(dp[i-1][j]+ap[n-i][k-j]));
}
if(u==2)
minusik[i]=1;
}
}
CALC();
vector<pair<int,int> > V;
for1(j,k)
for1(i,n)
{
if(S[i]!='_' && (i-C[j]+1)>minaj[i] && S[i-C[j]]!='X' && S[i+1]!='X')
if(dp[max(0,i-C[j]-1)][j-1]==1 && ap[max(n-i-1,0)][k-j]==1)
{
V.push_back(mp(i-C[j]+1,i));
}
}
for0(i,V.size()-1)
fo(j,V[i].first,V[i].second)
update(1,n,V[i].first,V[i].second,1,1);
for1(i,n)
if(get(1,n,i,1)==1)
plusik[i]=1;
string ANSWER;
for1(i,n)
{
if(S[i]!='.')
ANSWER+=S[i];
else
{
if(plusik[i]==1 && minusik[i]==0)
ANSWER+='X';
if(plusik[i]==0 && minusik[i]==1)
ANSWER+='_';
if(plusik[i]==1 && minusik[i]==1)
ANSWER+='?';
if(plusik[i]==0 && minusik[i]==0)
ANSWER+='X';
}
}
return ANSWER;
}
