#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
int dp[200003][103];
string S, F;
vector<int> Lazy;
vector<int> C, Fv;
vector<vector<int>> prs(3, vector<int>(200003, 0));
int n, m;
//ispossible dp
int prf(int i, int j, char c){
int x;
j = min(j, n-1);
if(c=='.')x=0;
if(c=='X')x=1;
if(c=='_')x=2;
return prs[x][j+1]-prs[x][i];
}
bool dpf(int i, int j){
bool res=true;
if(j==m && (i==n || i==n+1))return true;
if(i==n && j<m)return false;
if(j>m)return false;
if(i>n)return false;
if(dp[i][j]!=2)return (bool)dp[i][j];
int dsnc = prf(i, i+C[j]-1, '_');
int xsnc = prf(i, i+C[j]-1, 'X');
bool isag = (i+C[j]>=n || S[i+C[j]]=='.' || S[i+C[j]]=='_');
//cout << i << ' ' << j << ' ' << (int)isag << ' ' << S << '\n';
//cout << i << ' ' << j << ' ' <<dsnc << ' ' << dsnc2 << ' ' << xsnc << ' ' << S << '\n';
if(dsnc){
//am forced to be blank
if(S[i]=='X'){
res=false;
dp[i][j]=res;
return res;
}
bool x=dpf(i+1, j);
if(x){
//cout << i << " cas1\n";
Fv[i]|=1;
}
if(!x)res=false;
}
else if (S[i]=='X'){
if(dsnc || !isag){
res= false;
dp[i][j]=res;
return res;
}
bool y = dpf(i+C[j]+1, j+1);
if(y){
//cout << i << " cas2\n";
Fv[i]|=2;
Lazy[i]+=2;
Lazy[min(n, i+C[j])]-=2;
Fv[min(n, i+C[j])]|=1;
//lazyxtheredo
}
if(!y)res=false;
}
else{
bool x=dpf(i+1, j);
if(x){
Fv[i]|=1;
//cout << i << " cas3\n";
}
bool y = false;
if(!dsnc && isag){
y = dpf(i+C[j]+1, j+1);
if(y){
//cout << i << " cas4\n";
Fv[i]|=2;
Lazy[i]+=2;
Lazy[min(n, i+C[j])]-=2;
Fv[min(n, i+C[j])]|=1;
//lazyput there
}
}
if(!x && !y)res=false;
}
//cout << i << ' ' << j << ' ' << (int)res << '\n';
dp[i][j]=res;
return res;
}
string solve_puzzle(string s, vector<int> c) {
n=s.size();
m=c.size();
S=s;
C=c;
Fv.assign(n, 0);
Lazy.assign(n+1, 0);
vector<int> vals(3, 0);
prs[0][0]=0;
prs[1][0]=0;
prs[2][0]=0;
int i = 0;
for(int i = 0;i<200003;i++)for(int j = 0;j<103;j++)dp[i][j]=2;
for(auto thing:s){
if(s[i]=='.')vals[0]++;
if(s[i]=='X')vals[1]++;
if(s[i]=='_')vals[2]++;
i+=1;
prs[0][i]=vals[0];
prs[1][i]=vals[1];
prs[2][i]=vals[2];
}
for(int i = n;i<200003;i++){
prs[0][i]=vals[0];
prs[1][i]=vals[1];
prs[2][i]=vals[2];
}
dpf(0, 0);
int cl=0;
for(int i = 0;i<n;i++){
cl+=Lazy[i];
if(cl)Fv[i]|=2;
}
// for(int j=0;j<5;j++){
// for(int i = 0;i<25;i++){
// cout << dp[i][j] << ' ' ;
// }
// cout << '\n';
// }
// cout << '\n';
// for(auto thing:Fv){
// cout << thing<< ' ' ;
// }
// cout << '\n';
string ss;
for(int i = 0;i<n;i++){
if(Fv[i]==1)ss.push_back('_');
else if (Fv[i]==2)ss.push_back('X');
else ss.push_back('?');
}
return ss;
}
