#include "paint.h"
#include<bits/stdc++.h>
#include <cstdlib>
using namespace std;
bool dp1[200005][205], dp2[200005][205];
int n, prx[200005], k, pre[200005], canx[200005], cane[200005];
string ans;
string solve_puzzle(string s, vector<int> c)
{
n=s.length();
k=c.size();
s='0'+s;
c.insert(c.begin(), 0);
for(int i=1; i<=n; i++)
{
if(s[i]=='X') prx[i]=1;
if(s[i]=='_') pre[i]=1;
prx[i]+=prx[i-1];
pre[i]+=pre[i-1];
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=k; j++)
{
// [i-c[j]+1 ... i]
if(i-c[j]<0) continue;
if(j==1)
{
if(s[i]!='X') dp1[i][j]=dp1[i-1][j];
if(pre[i]-pre[i-c[j]]==0 and prx[i-c[j]]==0) dp1[i][j]=1;
}
else
{
if(s[i]!='X') dp1[i][j]=dp1[i-1][j];
if(pre[i]-pre[i-c[j]]==0 and dp1[i-c[j]-1][j-1] and s[i-c[j]]!='X') dp1[i][j]=1;
}
}
}
for(int i=n; i>=1; i--)
{
for(int j=k; j>=1; j--)
{
// [i ... i+c[j]-1]
if(i+c[j]-1>n) continue;
if(j==k)
{
if(s[i]!='X') dp2[i][j]=dp2[i+1][j];
if(pre[i+c[j]-1]-pre[i-1]==0 and prx[n]-prx[i+c[j]-1]==0) dp2[i][j]=1;
}
else
{
if(s[i]!='X') dp2[i][j]=dp2[i+1][j];
if(pre[i+c[j]-1]-pre[i-1]==0 and dp2[i+c[j]+1][j+1] and s[i+c[j]]!='X') dp2[i][j]=1;
}
}
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=k; j++)
{
// cout<<i<<' '<<j<<' '<<dp1[i][j]<<' '<<dp2[i][j]<<endl;
if(s[i]!='X' and dp1[i-1][j] and ((prx[n]-prx[i]==0 and j==k) or dp2[i+1][j+1])) cane[i]=max(cane[i], 1);
if(s[i]!='X' and (dp1[i-1][j-1] or (j==1 and prx[i-1]==0)) and dp2[i+1][j]) cane[i]=max(cane[i], 1);
if(i+c[j]-1<=n)
{
// [i ... i+c[j]-1]
if(s[i-1]!='X' and s[i+c[j]]!='X' and pre[i+c[j]-1]-pre[i-1]==0
and ((j==1 and prx[i-2]==0) or dp1[i-2][j-1]) and ((j==k and prx[n]-prx[i+c[j]]==0) or dp2[i+c[j]+1][j+1]))
canx[i]++, canx[i+c[j]]--;
}
}
}
for(int i=1; i<=n; i++)
canx[i]+=canx[i-1];
for(int i=1; i<=n; i++)
{
// cout<<"in cans : "<<cane[i]<<' '<<canx[i]<<endl;
if(s[i]=='.')
{
if(cane[i] and canx[i]) ans+='?';
else if(canx[i]) ans+='X';
else ans+='_';
}
else ans+=s[i];
}
return ans;
}
