#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
int dp[101][101];
string S, F;
vector<int> C, Fv;
vector<vector<int>> prs(3, vector<int>(104, 0));
int n, m;
//ispossible dp
int prf(int i, int j, char c){
int x;
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)return true;
if(i==n && j<m)return false;
if(j>m)return false;
if(i>n)return false;
if(j==m && prf(i, n, 'X')>0)return false;
if(j==m && prf(i, n, 'X')==0)return true;
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');
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)res=false;
}
else if (S[i]=='X'){
if(dsnc){
res= false;
dp[i][j]=res;
return res;
}
bool y = dpf(i+C[j], j+1);
if(!y)res=false;
}
else{
bool x=dpf(i+1, j);
bool y = false;
if(!dsnc) y = dpf(i+C[j], j+1);
if(!x && !y)res=false;
}
dp[i][j]=res;
return res;
}
bool solvable(string s, vector<int> c){
n=s.size();
m=c.size();
S=s;
C=c;
Fv.assign(n, 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<n;i++)for(int j = 0;j<m;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<=103;i++){
prs[0][i]=vals[0];
prs[1][i]=vals[1];
prs[2][i]=vals[2];
}
return dpf(0, 0);
}
string solve_puzzle(string s, vector<int> c) {
string res;
n=s.size();
for(int i = 0;i<n;i++){
if(s[i]!='.'){
res.push_back(s[i]);
continue;
}
s[i]='X';
int t = 0;
if (solvable(s, c))t|=1;
s[i]='_';
if (solvable(s, c))t|=2;
if(t==1)res.push_back('X');
else if (t==2)res.push_back('_');
else if (t==3) res.push_back('?');
s[i]='.';
}
return res;
}
