#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
int pre[200005];
vector<vector<bool>> happy_lama(string bati, vector<int>c1){
int n=bati.size();
int m=c1.size();
vector<vector<bool>>dp(n+1,vector<bool>(m+1));
dp[0][0]=1;
for(int i=1; i<=n; i++){
for(int j=0; j<=m; j++){
dp[i][j]=0;
int hi=0;
if(bati[i]!='X' && dp[i-1][j]==1){
hi=1;
}
if(j!=0){
//int a=0;
int pa=-1;
if(i-c1[j]+1>0){
pa=pre[i]-pre[i-c1[j]];
}
else{
pa=pre[i];
}
if(pa==-1 || pa>=1){
continue;
}
if(i<c1[j])continue;
if(i>c1[j]){
if(bati[i-c1[j]]!='X'){
if(dp[i-c1[j]-1][j-1]==1){
hi=1;
}
}
}
}
if(hi==1){
dp[i][j]=1;
}
}
}
return dp;
}
string solve_puzzle(string s, vector<int> c) {
string bati="*";
bati+=s;
vector<int>c1;
c1.push_back(0);
for(int i=0; i<c.size(); i++){
c1.push_back(c[i]);
}
int n=bati.size();
int m=c1.size();
for(int i=1; i<=n; i++){
if(bati[i]=='_'){
pre[i]++;
}
pre[i]+=pre[i-1];
}
vector<vector<bool>>dp1=happy_lama(bati,c1);
string a="*";
reverse(s.begin(),s.end());
a+=s;
vector<int>b;
b.push_back(0);
reverse(c.begin(),c.end());
for(int i=1; i<=c.size(); i++){
b.push_back(c[i]);
}
vector<vector<bool>>dp2=happy_lama(a,b);
// reverse(s.begin(),s.end());
// reverse(c.begin(),c.end());
vector<int>answ(n+1,0);
/*
_ 0
X 1
? 2
*/
map<int,pair<int,int>>mp;
for(int i=1; i<=n; i++){
int hi=0;
if(bati[i]=='_' || bati[i]=='X'){
if(bati[i]=='_'){
answ[i]=1;
}
continue;
}
for(int j=1; j<=m; j++){
int ha=0;
if(i==1)ha++;
if(i>1 && dp1[i-1][j]==1){
ha++;
}
if(i==n-1)ha++;
if(i<n-1 && dp2[n-i-1][m-j]==1){
ha++;
}
if(ha==2){
answ[i]=1;
}
int ichini=0;
if(i>2 && j>=1 && dp1[i-2][j-1]==1){
if(bati[i]!='X')ichini++;
}
else if(i==2 && j==0){
if(bati[i]!='X')ichini++;
}
else if(i<2 && j==0)ichini++;
int h=i+j;
if(h==n && j==m){
ichini++;
}
else if(h==n-1 && j==m){
if(bati[h]!='X')ichini++;
}
else{
if(bati[h]!='X' && i<n-1 && m-j-1>0 && dp2[n-i-1][m-j-1]==1)ichini++;
}
if(ichini==2){
mp[i].first++;
mp[h+1].second++;
}
}
}
string ixvi="";
int la=0;
for(int i=1; i<=n; i++){
if(bati[i]!='.'){
ixvi+=bati[i];
continue;
}
if(mp[i].first>0){
la+=mp[i].first;
}
if(mp[i].second>0){
la-=mp[i].second;
}
if(la==0){
if(answ[i]==1){
ixvi+='_';
}
else{
ixvi+='?';
}
}
else{
if(answ[i]==1){
ixvi+='?';
}
else{
ixvi+='X';
}
}
}
return ixvi;
}
