#include<bits/stdc++.h>
#include "paint.h"
using namespace std;
const int DECA=(1<<18),MAX_VAL=200*1000+5,MAX_BLOCS=100+5;
int nbVal,nbBlocs;
vector<int> listeBloc;
int etatDeb[MAX_VAL];
int cumu[2*DECA][2];
int memo[MAX_VAL][MAX_BLOCS];
int possiBlanc[MAX_VAL],possiNoir[MAX_VAL];
string rep;
int calcSom(int deb,int fin,int tab) {
if (deb==fin) {
return cumu[deb][tab];
}
if (deb%2==1) {
return cumu[deb][tab]+calcSom(deb+1,fin,tab);
}
if (fin%2==0) {
return cumu[fin][tab]+calcSom(deb,fin-1,tab);
}
return calcSom(deb/2,fin/2,tab);
}
int dyna(int pos,int idBloc) {
if (pos>=nbVal) {
if (pos==nbVal and idBloc==nbBlocs) {
return 1;
}
else {
return 0;
}
}
if (memo[pos][idBloc]!=-1) {
return memo[pos][idBloc];
}
memo[pos][idBloc]=0;
int ans;
if (etatDeb[pos]!=1) {
ans=dyna(pos+1,idBloc);
if (ans==1) {
memo[pos][idBloc]=1;
possiBlanc[pos]=1;
}
}
if (idBloc<nbBlocs and pos+listeBloc[idBloc]-1<nbVal and calcSom(DECA+pos,DECA+pos+listeBloc[idBloc]-1,1)==0
and (pos+listeBloc[idBloc]==nbVal or etatDeb[pos+listeBloc[idBloc]]!=1)) {
ans=dyna(min(pos+listeBloc[idBloc]+1,nbVal),idBloc+1);
if (ans==1) {
memo[pos][idBloc]=1;
possiNoir[pos]++;
possiNoir[pos+listeBloc[idBloc]]--;
possiBlanc[pos+listeBloc[idBloc]]++;
}
}
//cout<<pos<<" "<<idBloc<<" : "<<memo[pos][idBloc]<<endl;
return memo[pos][idBloc];
}
string solve_puzzle(string s,vector<int> c) {
nbVal=s.size();
listeBloc=c;
nbBlocs=listeBloc.size();
for (int i=0;i<nbVal;i++) {
if (s[i]=='.') {
etatDeb[i]=0;
}
if (s[i]=='X') {
etatDeb[i]=1;
cumu[DECA+i][0]++;
}
if (s[i]=='_') {
etatDeb[i]=2;
cumu[DECA+i][1]++;
}
//cout<<etatDeb[i]<<" ";
}
for (int i=DECA-1;i>0;i--) {
for (int j=0;j<=1;j++) {
cumu[i][j]=cumu[2*i][j]+cumu[2*i+1][j];
}
}
for (int i=0;i<MAX_VAL;i++) {
for (int j=0;j<MAX_BLOCS;j++) {
memo[i][j]=-1;
}
}
dyna(0,0);
for (int i=1;i<nbVal;i++) {
possiNoir[i]+=possiNoir[i-1];
}
for (int i=0;i<nbVal;i++) {
//cout<<i<<" : "<<possiNoir[i]<<" "<<possiBlanc[i]<<endl;
if (etatDeb[i]!=0) {
rep+=s[i];
}
else {
if (possiBlanc[i]>0 and possiNoir[i]>0) {
rep+='?';
}
else if (possiBlanc[i]>0) {
rep+='_';
}
else if (possiNoir[i]>0) {
rep+='X';
}
}
}
return rep;
}
