#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(v) (int)(v.size())
bool get(int n, int k, string s, vector<int> c){
if(k==0) return true;
string ret="_";
// cout << s << " ";
vector<int>sp(n+1);
for(int i=1;i<=n;i++){
sp[i]=sp[i-1];
if(s[i]=='_') sp[i]++;
}
int at=1, i=0;
while(at<=n){
if(i<k&&at+c[i]-1<=n&&s[at-1]!='X'&&sp[at+c[i]-1]-sp[at-1]==0&&s[at+c[i]]!='X'){
for(int j=1;j<=c[i];j++) ret.push_back('X'); // colocando o bloco
if(at+c[i]<=n) ret.push_back('_'); // dar espaco pro proximo
at=ret.size();
i++;
}else{
ret.push_back('_');
at++;
}
}
// cout << ret << " " << at << endl;
return i==k;
}
string solve_puzzle(string s, vector<int> c){
int n=s.size(), k=c.size();
s='_'+s+'_';
// reverse(c.begin(),c.end()); c.push_back(0); reverse(c.begin(),c.end());
vector<int>sp(n+1);
for(int i=1;i<=n;i++){
sp[i]=sp[i-1];
if(s[i]=='_') sp[i]++;
}
string ret="";
for(int i=1;i<=n;i++){
if(s[i]!='.'){
ret.push_back(s[i]);
continue;
}
string b=s;
int ini, fim;
for(int j=i;j>=1;j--){
if(s[j]=='_') break;
ini=j;
}
for(int j=i;j<=n;j++){
if(s[j]=='_') break;
fim=j;
}
bool aa=false;
for(int t=0;t<k;t++){
vector<int>c1, c2;
for(int j=0;j<t;j++) c1.push_back(c[j]);
for(int j=t+1;j<k;j++) c2.push_back(c[j]);
for(int j=ini;j<=i;j++){
string s1="", s2="";
for(int l=1;l<j-1;l++) s1.push_back(s[l]);
for(int l=j+c[t]+1;l<=n;l++) s2.push_back(s[l]);
s1='_'+s1+'_'; s2='_'+s2+'_';
// cout << i << " " << t << ' ' << s1 << " " << s2 << endl;
// cout << "c1: ";
// for(int x : c1) cout << x << " ";
// cout << endl;
// cout << "c2: ";
// for(int x : c2) cout << x << " ";
// cout << endl;
if(j+c[t]-1>=i&&j+c[t]-1<=fim){
aa=(aa||(get(sz(s1)-2,sz(c1),s1,c1)&&get(sz(s2)-2,sz(c2),s2,c2)));
// cout << aa << " " << j << " " << get(sz(s1)-2,sz(c1),s1,c1) << " " << get(sz(s2)-2,sz(c2),s2,c2) << endl;
}
}
}
b[i]='_';
bool bb=get(n,k,b,c);
if(aa&&bb) ret.push_back('?');
else if(aa) ret.push_back('X');
else if(bb) ret.push_back('_');
else ret.push_back('A');
}
return ret;
}
