#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
string get(int n, int k, string s, vector<int> c, vector<int> sp){
string ret="_";
int at=1, i=1;
while(at<=n){
if(i<=k&&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
ret.push_back('_'); // dar espaco pro proximo
at=ret.size();
i++;
}else{
ret.push_back('_');
at++;
}
}
return ret;
}
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]++;
}
vector<vector<int>>pd(k+1);
for(int i=1;i<=k;i++){
for(int j=1;j+c[i]-1<=n;j++){
// checar se o comeco pode ser em j
// condicoes: s[j-1]!='X', [j,j+c[i]-1] n tem '_', s[j+c[i]], s[j+c[i]]!='X'
if(s[j-1]!='X'&&sp[j+c[i]-1]-sp[j-1]==0&&s[j+c[i]]!='X') pd[i].push_back(j);
}
}
// cout << "yay" << endl;
vector<int>white(n+1,0), black(n+1,0), first(k+1), last(k+2);
first[1]=pd[1][0]; last[k]=pd[k].back();
for(int i=2;i<=k;i++){
for(int j : pd[i]){
if(first[i-1]+c[i-1]+1<=j){ // da pra coloca-lo e sobra um branco entre eles
first[i]=j;
break;
}
}
}
for(int i=k-1;i>=1;i--){
for(int j : pd[i]) if(j+c[i]+1<=last[i+1]) last[i]=j; // da pra me colocar e ainda sobra
}
for(int i=1;i<=k;i++){
for(int x : pd[i]){
// cout << first[i] << " " << x << " " << last[i] << endl;
if(first[i]<=x&&x<=last[i]){
// cout << x << " " << x+c[i] << endl;
black[x]++, black[x+c[i]]--;
}
}
}
// for(int i=1;i<=n;i++) cout << black[i] << " ";
// cout << endl;
// cout << "yey" << endl;
string ex=get(n,k,s,c,sp), ret="";
// cout << "yiy" << endl;
white[1]++; white[max(last[1],1)]--;
// for(int i=1;i<=k;i++) cout << first[i] << " " << last[i] << endl;
for(int i=1;i<k;i++){
white[first[i]+c[i]]++;
white[last[i+1]]--;
}
if(first[k]+c[k]!=n) white[first[k]+c[k]]++;
// for(int i=1;i<=n;i++) cout << white[i] << " ";
// cout << endl;
int sum_w=0, sum_b=0;
for(int i=1;i<=n;i++){
sum_w+=white[i]; sum_b+=black[i];
if(sum_w&&sum_b) ret.push_back('?');
else if(sum_w) ret.push_back('_');
else if(sum_b) ret.push_back('X');
else ret.push_back('A');
}
return ret;
}
// passa pro vazio?
