#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[20002][102];
int ap[20002][102];
int minqan[200002];
int minaj[200002];
int mindzax[200002];
int C[102];
string S;
int xdir1(int i,int j)
{
if((i-C[j]+1)>minaj[i] && C[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] && C[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];
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)
if(S[j]=='.')
plusik[j]=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+='?';
}
}
return ANSWER;
}
